/*有序数组：主要是为了提高查找的效率

  *查找：无序数组--顺序查找，有序数组--折半查找

  *其中插入比无序数组慢

  * */

 public class MyOrderedArray {

     private long[] arr;

     private int items;

     public MyOrderedArray(int max) {

         arr = new long[max];

         items = 0;

     }

     //数组中元素的个数

     public int size(){

         return items;

     }

     //折半查找

     public int find(long key){

         int low = 0;

         int high = items - 1;

         int mid;//变化的

         while(low <= high){

             mid = (low + high) / 2;

             if(key == arr[mid]){

                 return mid;

             }

             else if(key > arr[mid]){

                 low =  mid + 1;

             }

             else if(key < arr[mid]){

                 high = mid - 1;

             }

         }

         return -1;

     }

     //插入元素

     public void insert(long key){

         int i;

         for( i = 0; i < items; i++){ //先找到位置

             if(key < arr[i]){

                 break;

             }

         }

         for(int k = items;k>i; k--){   //移动元素

             arr[k] = arr[k -1];

         }

         arr[i] = key;//插入元素到找到的位置

         items++;

     }

     //删除元素--先判断找的位置合法--在判断

     public boolean delete(long key){

         int i = find(key);

         if(i == items){

             return false;

         }

         else{

             for(int k = i; k < items; k++){

                 arr[k] = arr[k + 1];

             }

             items--;

             return true;

         }

     }

     public void displayArray(){

         for(int i = 0;i < items;i++){

             System.out.print(arr[i] + " ");

         }

         System.out.println();

     }

 }