二分法查找

前几天CSDN上说只有10%程序员能写出正确的二分法查找代码

So.我在看过二分法查找方法后写了一个代码一次测试成功.

 

public class Dichotomy {
    private int[] array;
    //This Array is must be ordered
    public Dichotomy(int[] myarray){
        array = myarray;
    }
    public int find(int findKey){
        int startPoint = 0;
        int endPoint = array.length-1;
        int currentPoint = 0;
        int i=0;
        while(true){
            System.out.println("Search Time:"+(++i));
            currentPoint = (startPoint + endPoint)/2;
            if(array[currentPoint]==findKey){
                return currentPoint;// find it;
            }else if(startPoint > endPoint){
                return -1; //can't find it;
            }else {
                if(array[currentPoint]>findKey){
                    endPoint = currentPoint -1;
                }else{
                    startPoint = currentPoint +1;
                }
            }
        }
    }
    public static void main(String[] args) {
        int length = 10000000;
        int[] array = new int[length];
        long maxSearchTime = Math.round(Math.log10(length) * 3.322); //get Max Search Time
        System.out.println("Max Search Time is:"+maxSearchTime);
        int j =0;
        for(int i=0;i<array.length;i++){
            array[i]=i;
        }
        Dichotomy dich = new Dichotomy(array);
        int point = dich.find(6774477);
        System.out.println("Point is:"+point);
    }
}

 

 

对于有序数组,使用二分法查找数据比较的次数

范围 需要次数

10 4

100 7

1000 10

10000 14

100000 17

1000000 20

 

除了对特别小的数组外,二分法查找表现是非常优秀的.

每次对范围加倍可以创建出一个数列,它是2的幂,假设s表示步数,r表示范围,则有

r=2^s

当我们知道查找的范围r,求步数s时.就是相当于求某数指数函数的反函数即对数.则公式表示为:

s=log₂(r)

如何计算呢,大多数计算器都有log功能,通常是以10为底来求对数,但是通过结果乘以3.322可以转换成以2为底的对数

log10(100)=2;log2(100)=2乘以3.322 = 6.644 四舍五入为7正好是上面数据对照表100对应的7次.