彻底理解二分查找及其边界情况

二分查找是用于有序序列的高效查找算法,平均时间复杂度为 lg(n)。

有序序列可分为单调不减,例如 1, 2, 3, 3, 3, 5;以及单调不增序列,例如 5, 3, 3, 3, 2, 1。

也就是说,序列中可以出现重复的值,但是值的大小只能往一个方向变化。

序列中可能存在多个目标值,查找方式有两种:找第一次出现的位置、找最后一次出现的位置。

找第一次出现的位置

我们这里以单调不减序列为例。

思路:当 mid 处的值大于或等于目标值时,将右边界左移;只有 mid 处的值明确小于目标值时,才被动将左边界右移,这样就能尽可能地让右边界往左移动。

由于 Java 语言(C、C++、Python 等也一样)的除法是自动向下取整,因此中间位置 mid 会偏向左边界 left,所以 right = mid 而不是 right = mid - 1。因为只要 left 和 right 不相等,right = mid 一定会较原来的 right 左移,这样可以确保范围不断缩小。

下面是最后一次循环的典型情况,目标值为 3,right 指针略过了大于或等于 3 的位置,直到第一个 3 处,此时 mid 由于向下取整,等于 left,经过判断,发现 mid 处的值为 2,比目标值小,因此 left = mid + 1,移动到了右侧的位置上。

最终 left 和 right 相等,循环结束,该位置就是目标值第一次出现的位置(如果存在该目标值的话)。

/**
 * @author: Wray Zheng
 * @date: 2018-04-06
 */
public static void binarySearchFirst(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int mid;

    while (left < right) {
        mid = left + (right - left) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }

    if (arr[left] == target) return left;
    else return -1;
}

这里说一下,为什么 while 里的条件是 <,而不是 <=。一方面是我们想在循环外部判断最终的 left 位置是否是目标值,另一方面是如果循环条件允许 left = right,那么最后 mid = left = right,如果该处正好是目标值,那么 right 将始终等于 mid,不会再左移,就会陷入死循环。

找最后一次出现的位置

思路:当 mid 处的值小于或等于目标值时,将左边界右移;只有 mid 处的值明确大于目标值时,才被动将右边界左移,这样就能尽可能地让左边界往右移动。

虽然 Java 本身的除法是自动向下取整,但是我们可以先将被除数加一之后再做除法,这样就等价于向上取整,mid 会偏向右边界,因此 left = mid 可以确保左边界往右移动,缩小查找范围。

下面是最后一次循环的情况,目标值同样为 3,left 指针略过了小于等于 3 的位置,直到最后一个 3 处,mid 向上取整,等于 right,此时 mid 处的值为 5,比目标值大,因此 right = mid - 1,移动到左侧位置上。

于是,left 和 right 相等,循环终止,该位置就是目标值最后一次出现的位置。

/**
 * @author: Wray Zheng
 * @date: 2018-04-06
 */
public static void binarySearchLast(int[] arr, int target) {
    int left = 0;
    int right = ar.length - 1;
    int mid;

    while (left < right) {
        mid = left + (right - left + 1) / 2;
        if (arr[mid] > t) right = mid - 1;
        else left = mid;
    }

    if (arr[left] == target) return left;
    else return -1;
}

因为最后 left 和 right 相等,所以判断 arr[left] == targetarr[right] == target 是等价的。

对于单调不增序列

我相信讲完上面的例子,单调不增序列的情况我们都能按同样的逻辑分析出来了。

下面直接给出代码,不做赘述。

/**
 * @author: Wray Zheng
 * @date: 2018-04-06
 */
public static void binarySearchFirst(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int mid;

    while (left < right) {
        if (arr[mid] > t) left = mid + 1;
        else right = mid;
    }

    if (arr[left] == target) return left;
    else return -1;
}

public static void binarySearchLast(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int mid;

    while (left < right) {
        if (arr[mid] < t) right = mid - 1;
        else left = mid;
    }

    if (arr[left] == target) return left;
    else return -1;
}

相关文章

Loading Likes...

发表评论

电子邮件地址不会被公开。 必填项已用*标注