java二分法查找有序数组



二分法查找有序数组是java面试或者考试中经常遇到的算法之一。那么二分法查找的原理是什么呢？具体是怎么实现的呢？其实java数组Arrays类里面的一个方法–binarySearch(). 叫做为”二分查找”, 该方法的效率远远要高于线性查找, 但也存在着缺点, 例如查询对象一定要经过排序, 假如查询对象里面有多个元素相同时, 二分查找只能找到其中一个, 而且找到的这个元素不一定位于最前面或最后面. 下面对二分查找的原理作一总结:

java中使用二分搜索法来搜索指定的 int 型数组，以获得指定的值。必须在进行此调用之前对数组进行排序（通过sort(int[])方法）。如果没有对数组进行排序，则结果是不确定的。如果数组包含多个带有指定值的元素，则无法保证找到的是哪一个。

参数：

a – 要搜索的数组

key – 要搜索的值

返回：

假如包含在数组中，则返回搜索键的索引；否则返回 (-(插入点) – 1)。插入点 (mid)被定义为将键插入数组的那一点：即第一个大于此键的元素索引，如果数组中的所有元素都小于指定的键，则为a.length。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。

public static int binSearch(int a[], int key) {

int mid = a.length / 2;
if (key == a[mid]) {
return mid;
}

int start = 0;
int end = a.length – 1;
while (start <= end) {
mid = (end – start) / 2 + start;

if (key < a[mid]) { end = mid – 1; } else if (key > a[mid]) {
start = mid + 1;
} else {
return mid;
}
}


return -mid-1;
}

原理解析:

假定有一个经过升序排列的数组int a[], 二分查找首先会找到位于数组中间的数即插入点a[mid]与所要查找的数值key比较大小

key > a[mid] >>>> key可能在a[mid+1]至a[end]之间, 故start = mid+1继续进行循环

key < a[mid] >>>> key可能在a[mid-1]至a[start]之间, 故end = mid-1继续进行循环

key == a[mid] >>>> 已找到key, 返回插入点mid

优缺点分析:

二分查找每一次判断即可筛选掉一半数据, 效率比全遍历的线性查找的确高很多, 但是其只能返回一个值, 若查找数值在数组中存在多个, 其局限性立即显露出来, 还有若是数组中存在一些不可相互比较的元素(比如字符串), 无法根据其元素的自然顺序对数组进行排序, 因此结果是不确定的.

因此, 在选择查找方法时需要根据对所要查找的数组类型以及查找用途(若是仅查找是否存在在该数组中便可使用二分搜索, 若是查找该数在数组中的全部位置则忽略二分法)等多种因素考虑.

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 = 100000;
        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(49999);
        System.out.println("Point is:"+point);
    }
}
运行结果:
Max Search Time is:17
Search Time:1
Point is:49999
成功生成（总时间：1 秒）