查找算法之二分查找法

代码之神 2019-06-27

查找算法之二分查找法

思想

二分查找法的思想非常简单,对于一个有序数列,找它中间的元素,看是否是查找目标,如果不是,就看这个查找目标是小于还是大于中间元素,然后在对应的区间内重复上述过程。

算法

需要注意几个问题:

  • while 循环:while 循环的条件应该是 left < right 还是 left <= right 呢?

    • 这可以从我们设置的左右边界判断出来,我们设置的 left = 0, right = n - 1,因此 [left, right] 是一个闭区间,那么当 left = right 时,[left, right] 区间同样满足我们的设置,因此,这个循环内应该是 left <= right。
  • target 和 arr[mid] 的判断:当 target > arr[mid] 时,是应该 left = mid 还是 left = mid + 1 呢?

    • 这和在 while 中的判断是一个思路,当 target > arr[mid] 时,target 在 [mid + 1, r] 中,而非 [mid, r],因为显然此时 mid 已经不可能等于 target 了,因此我们不需要再比较 target 和 arr[mid]。
    • 同样地,当 target < arr[mid] 时,也是类似的判断。
  • 循环不变量:left 和 right 的定义十分重要,因为在后面我们要不断地维护这个定义,我们必须要保证是在 [left, right] 这个区间里寻找 target,这也就是 循环不变量,意思就是 left 和 right 的值虽然一直在变化,但是有一个声明 在 [left, right] 区间内寻找 target 是永远不变的,只要我们维护住这个 循环不变量,那么就可以保证我们的算法是正确的。当然,这里你也可以定义成 left = 0, right = n,即[left, right),那么此时定义就发生了变化,相应地,在 while 中为了维护这个定义,我们需要把条件改成 left < right,因为当 left = right 时,显然 [left, right)是错误的,后面再查找时也要做相应的修改。
private int binarySearch(T arr[], int n, T target) {

        int left = 0, right = n - 1; // 在 [left, right] 区间内寻找 target
        
        while (left <= right) { // 当 left = right 时,区间 [left, right] 仍然有效
            int mid = (left + right) / 2;
            if (arr[mid] == target)
                return mid;
            if (target > arr[mid])
                left = mid + 1; // target 在 [mid+1, r] 中
            else
                right = mid - 1; // target 在 [left, mid - 1] 中
        }

        return -1;
    }

不知道到这里大家有没有发现一个 bug

因为 left 和 right 都是 int,所以当值足够大时,在计算 mid = (left + right) / 2 时可能会发生整型溢出!

因此,为了避免这个问题,我们使用减法来计算。

完全正确的二分查找法

public int binarySearch(T[] arr, int n, T target) {

        int left = 0, right = n - 1; // 在 [left, right] 区间内寻找 target

        while (left <= right) { // 当 left = right 时,区间 [left, right] 仍然有效
            int mid = left + (right - left) / 2;
            if (arr[mid].compareTo(target) == 0)
                return mid;
            if (target.compareTo(arr[mid]) > 0)
                left = mid + 1; // target 在 [mid+1, r] 中
            else
                right = mid - 1; // target 在 [left, mid - 1] 中
        }

        return -1;
    }

测试

我们可以写一个 Util 来帮助我们生成测试用例

ArrayUtil.java

public static Integer[] generateSortedArray(int n) {

        assert n > 0;

        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }

        return arr;
    }

BinarySearch.java

public static void main(String[] args) {

        BinarySearch<Integer> bs = new BinarySearch<Integer>();
        int n = (int)Math.pow(10, 7); // 用 10,000,000 数据测试
        Integer[] data = ArrayUtil.generateSortedArray(n);

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < n; i++)
            if (i != bs.binarySearch(data, n, i))
                throw new IllegalStateException("find i failed");
        long endTime = System.currentTimeMillis();

        System.out.println("Binary Search success!");
        System.out.println("Time cost: " + (endTime - startTime) + "ms");
    }

完整代码:github: My-Notes/algorithm(Java)/01-binarySearch/src/

相关推荐