欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找细节讨论

程序员文章站 2024-03-20 17:15:04
...

二分查找框架

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列

public int binarySearch (int[] nums, int target) {
    int left = 0;
    int rigt = ...;
    while (left ... rigt) {
        int mid = (left + rigt) / 2;
        if (nums[mid] == target) {
            return mid;
        }else if (nums[mid] < target) {
            left = ...;
        }else if (nums[mid] > target) {
            rigt = ...;
        }
    }
    return -1;
}

…代表需考虑的细节位置,如:while循环中的不等号是否应该带等号,left是否应该加一,right是否应该减一等。

所有算法都有一点需注意:计算 mid 时需要技巧防止溢出同时加快运算速度,
建议写成: mid = start + ((end - start) >> 1)

寻找一个数(有序数组 nums = [1,2,2,2,3],target = 2,此算法返回的索引是 2)

场景描述:即搜索一个数,如果存在,返回其索引,否则返回 -1。

public int binarySearch (int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while(left <= right) {
        int mid = start + ((end - start) >> 1);
        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 的赋值是 nums.length - 1,即最后一个元素的索引,而不是 nums.length。

while(left <= right)的终止条件是 left == right + 1,写成区间的形式就是 [right + 1, right],或者带个具体的数字进去 [3, 2],可见这时候搜索区间为空,因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的,直接返回 -1 即可。

while(left < right)的终止条件是 left == right,写成区间的形式就是 [right, right],或者带个具体的数字进去 [2, 2],这时候搜索区间非空,还有一个数 2,但此时 while 循环终止了。也就是说,索引 2 没有被搜索,如果这时候直接返回 -1 就可能出现错误。
非要用 while(left < right) 也可以,只需加上以下代码:

//...
while(left < right) {
    // ...
}
//最后加一个遗漏检查
return nums[left] == target ? left : -1;

寻找左侧边界的二分搜索(有序数组 nums = [1,2,2,2,3],target = 2,此算法返回的索引是 1)

场景描述:即搜索一个数,如果存在,返回其左边界索引,否则返回 -1。

public int binarySearch (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;
}

上述代码中:为什么 while(left < right) 而不是 <= ?
因为初始化 right = nums.length 而不是 nums.length - 1 。因此每次循环的是 [left, right) 左闭右开。while(left < right) 终止的条件是 left == right,此时搜索区间 [left, left) 恰巧为空,所以可以正确终止。

为什么没有返回 -1 的操作?如果 nums 中不存在 target 这个值,怎么办?
函数的返回值(即 left 变量的值)取值区间是闭区间 [0, nums.length],所以我们简单添加两行代码就能在正确的时候 return -1。

while (left < right) {
    //...
}
//跳出left值只能为0 或者  nums.length
// target 比所有数都大,即 nums.length
if (left == nums.length) return -1;
// 类似之前算法的处理方式
return nums[left] == target ? left : -1;

为什么该算法能够搜索左侧边界?
找到 target 时不要立即返回,而是缩小区间右边界 right,在区间 [left, mid) 中继续搜索,即不断向左收缩,达到锁定左侧边界的目的。
很重要:!!! 可以看到当mid为target或者大于target的操作,其实是一样的,都是right=mid,
所以最后返回的left,其实是数组中,大于等于target的元素的第一个位置。

寻找右侧边界的二分搜索(有序数组 nums = [1,2,2,2,3],target = 2,此算法返回的索引是 3)

场景描述:即搜索一个数,如果存在,返回其右边界索引,否则返回 -1。

public int binarySearch (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) {
            left = mid + 1; 
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; 
}

如果 nums 中不存在 target 这个值,怎么办?
**while 循环结束时,nums[left] 一定不等于 target 了,而 nums[left - 1]可能是target。**类似前面的左侧边界搜索,因为 while 的终止条件是 left == right,就是说 left 的取值范围是 [0, nums.length],所以可以添加两行代码,正确地返回 -1。

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

最后总结

寻找具体的数 寻找数的左侧边界 寻找数的右侧边界
初始条件 right = nums.length - 1 right = nums.length right = nums.length
搜索区间 [left, right] [left, right) [left, right)
while的条件 while (left <= right) while (left < right) while (left < right)
left的处理 mid+1 mid+1 mid+1
right处理 mid-1 mid mid
nums[mid] == target 立即返回索引 right = mid left = mid + 1
遗漏处理方法 if (left == nums.length) return -1;return nums[left] == target ? left : -1; if (left == 0) return -1; return nums[left-1] == target ? (left-1) : -1;
相关标签: Java面试