二分查找算法的详细讲解

二分算法是一个较高效率的查找算法，但是二分法中的细节却经常使人感到懵圈。有一次看到一位大神整理的二分算法细节分析，个人觉得挺好的，借鉴大神的讲解，我也大致整理了一些内容。

二分算法常用情景大致分为三种：寻找一个数、寻找左侧边界、寻找右侧边界。

情景一：寻找一个数
这个场景是最常见的，是大家最熟悉的。即搜索一个数，如果存在，返回其索引，否则返回 -1。

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 
            right = mid - 1;      	// 注意
        }
    }
    return -1;
}

问题一：为什么 while 循环的条件中是 <=，而不是 < ？

答：初始化 right 的赋值是 nums.length-1，即最后一个元素的索引，而不是 nums.length。因此，搜索区间为 [left, right]，当搜索区间缩小为 [left, left] 即（left == right），还有一个数字 nums[left] 需要被判断，若循环的终止条件为 < ，这时会遗漏一个数字，因此，循环的结束条件应该是 <= 。

问题二： 为什么 left = mid + 1，right = mid - 1？有的代码是 right = mid 或者 left = mid。

答：本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，下一步的搜索区间当然是 [left, mid - 1] 或者 [mid + 1, right]。因为 mid 已经搜索过，应该从搜索区间中去除。因此，需要进行 left = mid + 1、right = mid - 1，而不是 right = mid 、left = mid。

情景二：寻找左侧边界

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 {
            right = mid; 		// 注意
        }
    }
    return left;
}

问题一：为什么 while(left < right) 而不是 <= ?

答： right = nums.length 而不是 nums.length - 1 。因此每次循环的搜索区间是[left, right) 左闭右开。while(left < right) 终止的条件是 left == right，此时搜索区间 [left, left) 为空，所以可以正确终止。

问题二：为什么 left = mid + 1，right = mid ？和之前的算法不一样？

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

问题三：为什么该算法能够搜索左侧边界？

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

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

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

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

答：当 left == nums.length 时，即 target 比所有数都大，返回 -1。否则，若nums[left] 等于 target，返回 left，否则，返回 -1.

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

注意：循环的终止条件是 left == right，因此，返回 left 和 right 是一样的。

情景三：寻找右侧边界

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 {
            right = mid;
        }
    }
    return left - 1;			// 注意
}

问题一：为什么这个算法能够找到右侧边界？

答：关键点：

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

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

问题二：为什么最后返回 left - 1 而不像左侧边界的函数，返回 left？

答：while 循环的终止条件是 left == right，所以返回 left 和 right 是一样的。
因为是右侧边界，我们对 left 的更新必须是 left = mid + 1，也就意味着 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。因此返回 left-1。

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

答：当 left == 0（即 right = = 0），left 从未向右趋近，也就是 target 始终大于 nums 中的每个数，意味着不存在 target。
当 nums[left-1] != target ，也就是 target 不存在。

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

最后

以上就是失眠书包为你收集整理的二分查找算法的详细讲解的全部内容，希望文章能够帮你解决二分查找算法的详细讲解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。