java数组之二分法查找

认识：

　　猜字游戏

步数	所猜的数	结果	可能值的范围
0			1~100
1	50	太高	1~49
2	25	太低	26~49
3	37	太高	26~36
4	31	太低	32~36
5	34	太高	32~33
6	32	太低	33~33
7	33	正确

二分法要求：

　　有序数列

有序数组的java代码：

  1 package com.test;
  2 
  3 /**
  4  * 二分查找
  5  * @author jingxin
  6  *
  7  */
  8 public class Test {
  9 
 10     public static void main(String[] args) {
 11 
 12         OrdArray array = new OrdArray(5);
 13         
 14         array.insert(21);
 15         array.insert(1);
 16         array.insert(3);
 17         array.insert(4);
 18         array.insert(10);
 19         
 20         array.display();
 21         
 22         int i = array.find(3);
 23         System.out.println("二分查找："+i);
 24         
 25         array.delete(1);
 26         
 27         array.display();
 28 
 29     }
 30     
 31     
 32     
 33 
 34 }
 35 
 36 
 37 class OrdArray{
 38     private long[] a; //数组
 39     private int nElems;  //数组下标
 40     
 41     public OrdArray(int max){
 42         a = new long[max]; //初始化数组
 43         nElems = 0;
 44     }
 45     
 46     /**
 47      * 返回数组的长度
 48      * @return
 49      */
 50     public int size(){
 51         return nElems;
 52     }
 53     
 54     /**
 55      * 二分查找
 56      * @param searchKey 待查找的数
 57      * @return
 58      */
 59     public int find(long searchKey){
 60         int lowerBound = 0; // 二分起始下标
 61          int upperBound = nElems -1; // 二分终点下标
 62         int  curIn; // 二分对半下标
 63         
 64         while(true){
　　
　　　　　　　　　 //对于偶数个数据项，中间值只取整数，不影响查找结果　　
 65             curIn = (lowerBound + upperBound)/2;
 66             if(a[curIn] == searchKey){
 67                 return curIn;  // 找到了
 68             } else if(lowerBound > upperBound){
 69                 return nElems; // 找不到返回元素个数
 70             } else{
 71                 if(a[curIn] < searchKey){
 72                     lowerBound = curIn + 1;  
 73                 } else{
 74                     upperBound = curIn - 1;
 75                 }
 76             }
 77         }
 78         
 79     }
 80     
 81     /**
 82      * 升序添加数组元素
 83      * @param value
 84      */
 85     public void insert(int value){
 86         int i;
 87         for (i = 0; i < nElems; i++) {
 88             if(a[i] > value){  // 线性查找,i存放符合条件的顺序元素
 89                 break;
 90             }
 91         }
 92         for (int k = nElems; k>i; k--) { // 移动较大的数往上移 
 93             a[k] = a[k-1]; 
 94         }
 95         a[i] = value;  
 96         nElems++;
 97     }
 98     
 99     /**
100      * 删除数组元素
101      * @param value
102      * @return
103      */
104     public boolean delete(long value){
105         int i = find(value);
106         // eg:5个数则，nElems=5，而i只能是0~4
107         if(i == nElems){
108             return false; // 该元素不存在
109         } else{
110             for (int k = i; k < nElems-1; k++) { // 将更大的数往下移
111                 a[k] = a[k+1];
112             }
113             nElems--;
114             return true;
115         }
116         
117         
118         
119         
120     } 
121     
122     /**
123      * 查看数组
124      */
125     public void display(){
126         for (int i = 0; i < nElems; i++) {
127             System.out.print(a[i]+ " ");
128         }
129         System.out.println("");
130     }
131     
132 }

二分查找所需的比较次数对照表：

范围	所需比较次数	该次数能查找的最大范围
10	4	16=2^4
100	7	128=2^7
1千	10	1024=2^10
1万	14	2^14
10万	17	2^17
100万	20	2^20
1000万	24	2^24
1亿	27	2^27