查找-二分查找

写在前边的话：今天记录一下关于算法中 二分查找 的一些理解和心得。
主要分为以下几个方面分享

• 二分查找的思想
• 实现方式
• 时间复杂度

---

二分查找的思想

1：在一个 有序且采用顺序结构存储的线性表中，取 中间记录 与 给定对象 相比较。
2：若 中间记录与给定对象值 相等，则表示查找成功，并返回中间记录的下标。
3：若 中间记录比给定对象值 小，则在中间记录的 右半区继续查找。
4：若 中间记录比给定对象值 大，则在中间记录的 左半区继续查找。
5：不断重复上述1~4步骤，直至查找成功或者失败为止。

---

实现方式

    public static void main(String[] args){
        Integer[] array = Util.createRandomArray(100, 20);
        Util.sysSort(array);

        Integer[] array1 = Arrays.copyOf(array, array.length);
        Integer[] array2 = Arrays.copyOf(array, array.length);

        Util.print(Arrays.toString(array) + "================================", "数据源");
        int searchNum = 37;

        int index = binarySearch(array1, searchNum);
        Util.print("结果:" + (index >= 0 ? "找到" + searchNum + ",它的下标为:" + index : "没找到！"), "binarySearch()");

        Util.print("================================", "");
        int index2 = Util.sysBinarySearch(array2, searchNum);
        Util.print("结果:" + (index2 >= 0 ? "找到" + searchNum + ",它的下标为:" + index2 : "没找到！"), "Util.sysBinarySearch()");

    }

    private static int binarySearch(Integer[] array, Integer searchNum){
        Util.checkArrayISNull(array);
        Util.checkSrcIsNull(searchNum);

        int searchNumIndex = -1;

        int low = 0; //记录查找区域的最小边界值
        int high = array.length - 1; //记录查找区域的最大边界值
        while (low <= high){
            int mid = (low + high) >> 1; //中间记录的下标

            System.out.println("low:" + low + ", high:" + high + ", mid:" + mid);

            if(searchNum < array[mid]){ //给定值比中间记录小，说明给定值在中间记录的左半区域，此时high对应的下标应该是mid的前一位数据对应的下标
                high = mid - 1;
            } else if(searchNum > array[mid]){ //给定值比中间记录大，说明给定值在中间记录的右半区域，此时low对应的下标应该是mid的后一位数据对应的下标
                low = mid + 1;
            } else { //查找成功
                searchNumIndex = mid;
                break;
            }
        }

        return searchNumIndex;
    }

    public static int sysBinarySearch(Integer[] src, Integer searchNum){
        checkArrayISNull(src);
        checkSrcIsNull(searchNum);

        int index = -1;

        index = Arrays.binarySearch(src, searchNum);

        return index;
    }

log

数据源:[6, 10, 12, 17, 18, 24, 26, 33, 37, 42, 46, 47, 51, 55, 66, 66, 69, 70, 82, 95]================================
low:0, high:19, mid:9
low:0, high:8, mid:4
low:5, high:8, mid:6
low:7, high:8, mid:7
low:8, high:8, mid:8
binarySearch():结果:找到37,它的下标为:8
:================================
Util.sysBinarySearch():结果:找到37,它的下标为:8

---

时间复杂度

O(logn)