二分查找

二分查找学习笔记（一）

二分查找代码框架

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 ...;
}

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;
}

一

初始化 right 的赋值确立「搜索区间」(search space)

nums.length - 1，相当于两端都闭区间 [left, right]，循环条件是<=

nums.length      ，相当于左闭右开区间 [left, right)，循环条件是<

二

停止搜索时刻：找到目标值时

if(nums[mid] == target)
        return mid;

 停止搜索时刻：未找到目标值时，搜索区间为空时停止，返回值为-1

while(left <= right)的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，这时候搜索区间为空。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

while(left < right)的终止条件是 left == right，写成区间的形式就是 [right, right]，这时候搜索区间非空，但此时 while 循环终止了，如果这时候直接返回 -1 就可能出现错误。

补丁：

while(left < right) {...}
return nums[left] == target ? left : -1;

三

mid != target 时，确定下一步的搜索区间（nums.length - 1时）

搜索 [left, mid - 1] 或者 [mid + 1, right] 

所以 left = mid + 1，right = mid - 1;

四

算法缺陷

有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。

二分查找变种

 寻找左边界

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;
}

异常处理：nums中不存在target情况

while (left < right){...}
// target 比所有数都大
if (left == nums.length) return -1;
// 类似之前算法的处理方式
return nums[left] == target ? left : -1;

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

搜索左侧边界关键在于对于 nums[mid] == target 这种情况的处理

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

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

寻找右边界

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; // 注意

返回 right - 1 是搜索右侧边界的一个特殊点，关键在这个条件判断：

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

 异常处理：

while (left < right) { ... }
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;

 总结

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

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

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

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

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

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

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

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

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

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

参考

详解二分查找算法 - murphy_gb - 博客园 (cnblogs.com) 

相关

标签