java折半查找算法

折半查找，可以对数据较多的序列提高查找速度，但有一个重要的前提

• 查找的序列必须有序

此外，折半查找仅能判断序列中是否存在“某个数据”。

基本思想

判断序列中间数据是否等于查找数据，如果等于则返回序列中间下标

若中间数据大于(假设升序)查找数据，则舍弃右侧范围，反之舍弃左侧范围

循环上述的判断数据、舍弃范围，假设范围为1还没找到，说明不存在数据

代码实现

以数组为例，以下标操作，则起始范围是：[0, length-1]

定义low表示左侧范围，high表示右侧范围，mid表示中间

舍弃左侧范围时，low=mid+1，

舍弃右侧范围时，high=mid-1

    public static void main(String []args){

        int[] arr = {1,2,5,8,11};
        int index = binSearch(arr,0,arr.length-1,7);  // 查找7
        int index2 = binSearch(arr,0,arr.length-1,11);  //查找11
        System.out.println(index);
    }
    /**
     *
     * @param arr 数据数组
     * @param low 起始下标
     * @param high 终止下标
     * @param k 查询数据
     * @return 数据所在下标，或-1
     */
    static int binSearch(int[] arr, int low, int high, int k){

        int mid;
        while(low <= high){

            mid = (low+high)/2;
            if(arr[mid]==k){
                return mid;
            }
            else if(arr[mid]>k){
                high = mid-1;
            }else{
                low = mid+1;
            }
        }
        return -1;
    }

程序输出结果：

• -1
• 4