有序数组的二分查找

  演示：有序数组的二分查找方法
　1 /**
  2  * 测试类
  3  * @author mackxu
  4  *
  5  */
  6 public class MyArrayApp {
  7     
  8     public static void main(String[] args) {
  9         // TODO Auto-generated method stub
 10         MyArray arr = new MyArray(10);
 11         //System.out.print(arr.find(11));            //out: 0
 12         //arr.display();
 13         arr.insert(3);
 14         arr.insert(13);
 15         arr.insert(35);
 16         arr.insert(29);
 17         arr.insert(15);
 18         arr.insert(66);
 19         arr.insert(89);
 20         
 21         arr.display();
 22         arr.delete(13);
 23         arr.display();
 24         
 25         //double [] a = new double[4];        //0.0
 26         //String [] a = new String[4];        //null
 27         boolean[] a = new boolean[4];        //false
 28         for (boolean e:a)
 29             System.out.print(e+" | ");
 30     }
 31 
 32 }
 33 
 34 /**
 35  * 有序数组
 36  * 二分查找法
 37  * 小结：
 38  * 数组中删除元素只需要向前移动位置就行
 39  * for迭代器可以输出数组
 40  * 数组建立时有默认初值
 41  * double[] a = new double[4];        //0.0
 42  * String[] a = new String[4];            //null
 43  * boolean[] a = new boolean[4];        //false
 44  * @author mackxu
 45  *
 46  */
 47 class MyArray {
 48     
 49     private int[] a;
 50     private int nElems = 0;
 51     private int spaceSize;
 52     
 53     public MyArray(int max) {
 54         //默认情况是a中包含max个0
 55         a = new int[max];            //创建max元素的数组
 56         spaceSize = max;            //开辟的空间大小
 57     }
 58     /**
 59      * @return 返回数组的元素个数
 60      */
 61     public int size() {
 62         
 63         return nElems;        
 64     }
 65     
 66     //向数组中添加元素
 67     public void insert(int value) {
 68         //判断数组是否已经满了
 69         if (spaceSize <= nElems){
 70             System.out.println("已经满了,不能再加了！！");
 71             return;
 72         }
 73         int i;
 74         //找到插入的位置
 75         for(i=0; i<nElems; i++) {
 76             if (a[i] > value)
 77                 break;
 78         }
 79         //腾出位置等待插入
 80         for (int k = nElems; k>i; k--) {
 81             a[k] = a[k-1];
 82         }
 83         //插入元素
 84         a[i] = value;
 85         nElems ++;
 86     }
 87     //删除指定的元素
 88     public boolean delete(int value) {
 89         
 90         //查找要删除的数组元素下标
 91         int i = find(value);
 92         if (i == size()) {
 93             System.out.println("删除错误：数组中不存在值为"+value+"元素！！");
 94             return false;
 95         }
 96         //从下标为i的元素以后都向前移动一个位置
 97         for (int j=i+1; j<nElems; j++)
 98             a[j-1] = a[j];
 99         /*//j<nElems-1 检测a[j+1]是否越界
100         for (int j=i; j<nElems-1; j++)
101             a[j] = a[j+1];*/            
102         //数组元素减1
103         -- nElems;
104         return false;
105     }
106     /**
107      * 二分查找有序数组中的特定元素
108      * @param int value
109      * @return 返回元素的下标，否者返回数组的长度
110      */
111     public int find(int value) {
112         int lBound = 0, rBound = nElems-1, curIn;
113         
114         while(true) {
115             curIn = (lBound+rBound) / 2;
116             //找到要查询的值,返回其下标
117             if (a[curIn] == value)
118                 return curIn;
119             //数组中没有该元素, 停止循环
120             if (lBound > rBound) 
121                 return nElems;
122             if (a[curIn] < value) {
123                 lBound = curIn + 1;
124             } else {
125                 rBound = curIn - 1;
126             }
127         }
128     }
129     
130     /**
131      * 输出从小到大的数组元素
132      */
133     public void display() {
134         if (nElems == 0) {
135             System.out.println("一个元素也没有");
136             return;
137         }
138         /*for (int elem : a) {
139             System.out.print(elem+" ");
140         }*/
141         for (int i = 0; i < nElems; i++) {
142             System.out.print(a[i]+" ");
143         }
144         System.out.println();        
145     }
146 }