二分查找判断条件问题

基本的二分查找框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int nums[], int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = (right + left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

有几点需要注意：

  • right取值
  • while循环结束条件
  • 缩小搜索区间

寻找一个数

闭区间内搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int nums[], int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) { // 注意
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

while的条件和right的取值。根据搜索区间的不同，如果包含right，则最后搜索区间会缩小到[left,right] 此时有可能相等，如不包含right，[left,right)最后一次搜索的值只有left。停止条件要和搜索范围相匹配。

左闭右开区间搜索

如果是左闭右开区间如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int nums[], int target) {
    int left = 0; 
    int right = nums.length; // 下标不包含右边

    while(left < right) { // 注意结束条件
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // mid比较过之后不再比较
        else if (nums[mid] > target)
            right = mid; // 下标不包含右边
        }
    return -1;
}

不包含right下标的搜索

算法缺陷

存在一个数组[1,2,3,3,3,3,4,4,4,4,5,5,]此算法只能搜索到其中一个数值的下标。无法搜索一个范围

寻找左边界的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int left_bound(int nums[], int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

*1.*为什么 while(left < right) 而不是 <= ?

用相同的方法分析，因为初始化 right = nums.length 而不是 nums.length - 1 。因此每次循环的「搜索区间」是 [left, right) 左闭右开。

while(left < right) 终止的条件是 left == right，此时搜索区间 [left, left) 恰巧为空，所以可以正确终止。

2. 为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办？

左侧边界的含义：

比如对于有序数组 nums = [2,3,5,7], target = 1，算法会返回 0，含义是：nums 中小于 1 的元素有 0 个。如果 target = 8，算法会返回 4，含义是：nums 中小于 8 的元素有 4 个。

综上所述，函数的返回值（即 left 变量的值）取值区间是闭区间 [0, nums.length]。

3. 为什么 left = mid + 1，right = mid ？和之前的算法不一样？

因为我们的「搜索区间」是 [left, right) 左闭右开，所以当 nums[mid] 被检测之后，下一步的搜索区间应该去掉 mid 分割成两个区间，即 [left, mid) 或 [mid + 1, right)。

4. 为什么该算法能够搜索左侧边界？

关键在于对于 nums[mid] == target 这种情况的处理：

1
2
if (nums[mid] == target)
    right = mid;

可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

寻找右边界的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int right_bound(int nums[], int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

1. 为什么这个算法能够找到右侧边界？

1
2
if (nums[mid] == target) {
       left = mid + 1;

当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的下界 left，使得区间不断向右收缩，达到锁定右侧边界的目的。

2. 为什么最后返回 left - 1 而不像左侧边界的函数，返回 left？而且我觉得这里既然是搜索右侧边界，应该返回 right 才对。

while 循环的终止条件是 left == right，所以 left 和 right 是一样的，你非要体现右侧的特点，返回 right - 1 好了。

至于为什么要减一，这是搜索右侧边界的一个特殊点，关键在这个条件判断：

1
2
3
if (nums[mid] == target) {
    left = mid + 1;
    // 这样想: mid = left - 1

因为我们对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left - 1] 可能是 target。

至于为什么 left 的更新必须是 left = mid + 1，同左侧边界搜索，就不再赘述。

总结

第一个，最基本的二分查找算法：

1
2
3
4
5
6
7
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1

因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回

第二个，寻找左侧边界的二分查找：

1
2
3
4
5
6
7
8
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid+1 和 right = mid

因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界

第三个，寻找右侧边界的二分查找：

1
2
3
4
5
6
7
8
9
10
11
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid+1 和 right = mid

因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界

又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一

平均查找长度（Average Search Length)

ASL（Average Search Length），即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度。