标签搜索

目 录CONTENT

文章目录

二分查找详解.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 6 阅读 / 4,372 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

二分查找详解

@[toc]

二分法我们都很熟悉,但是我们都可以充分利用二分法来解决更多的问题吗?

二分法的⼏个最常⽤的⼆分查找场景: ==寻找⼀个数、 寻找左侧边界、 寻找右侧边界==。

一、 寻找⼀个数(基本的⼆分搜索)

这个场景是最简单的, 肯能也是⼤家最熟悉的, 即搜索⼀个数, 如果存在,
返回其索引, 否则返回 -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 if (nums[mid] > target)
			right = mid - 1; // 注意
	}
	return -1;
}
  •  1、 为什么 while 循环的条件中是 <=, ⽽不是 < ?

答: 因为初始化 right 的赋值是 nums.length - 1, 即最后⼀个元素的索引, ⽽不是 nums.length。这⼆者可能出现在不同功能的⼆分查找中, 区别是: 前者相当于两端都闭区间 [left, right], 后者相当于左闭右开区间 [left, right), 因为索引⼤⼩为nums.length 是越界的。我们这个算法中使⽤的是前者 [left, right] 两端都闭的区间。 这个区间其实就是每次进⾏搜索的区间。

什么时候应该停⽌搜索呢? 当然, 找到了⽬ 标值的时候可以终⽌:

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

但如果没找到, 就需要 while 循环终⽌, 然后返回 -1。 那 while 循环什么时候应该终⽌? 搜索区间为空的时候应该终⽌, 意味着你没得找了, 就等于没找到嘛。

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

while(left < right) 的终⽌条件是 left == right, 写成区间的形式就是 [left,right], 或者带个具体的数字进去 [2, 2], 这时候区间⾮空, 还有⼀个数 2,但此时 while 循环终⽌了。 也就是说这区间 [2, 2] 被漏掉了, 索引 2 没有被搜索, 如果这时候直接返回 -1 就是错误的。

当然, 如果你⾮要⽤ while(left < right) 也可以

while(left < right) {
// ...
} 
return nums[left] == target ? left : -1;
  •  2、 为什么 left = mid + 1, right = mid - 1? 我看有的代码是 right = mid 或者left = mid, 没有这些加加减减, 到底怎么回事, 怎么判断?

答: 这也是⼆分查找的⼀个难点, 不过只要你能理解前⾯的内容, 就能够很容易判断。

刚才明确了「搜索区间」 这个概念, ⽽且本算法的搜索区间是两端都闭的,即 [left, right]。 那么当我们发现索引 mid 不是要找的 target 时, 如何确定下⼀步的搜索区间呢?

当然是 [left, mid - 1] 或者 [mid + 1, right] 对不对? 因为 mid 已经搜索过, 应该从搜索区间中去除

  •  3、 此算法有什么缺陷?

答: ⾄此, 你应该已经掌握了该算法的所有细节, 以及这样处理的原因。 但是, 这个算法存在局限性。

⽐如说给你有序数组 nums = [1,2,2,2,3], target = 2, 此算法返回的索引是2, 没错。 但是如果我想得到 target 的左侧边界, 即索引 1, 或者我想得到target 的右侧边界, 即索引 3, 这样的话此算法是⽆法处理的。这样的需求很常⻅。 你也许会说, 找到⼀个target, 然后向左或向右线性搜索不⾏吗? 可以, 但是不好, 因为这样难以保证⼆分查找对数级的复杂度了

⼆、 寻找左侧边界的⼆分搜索

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 这个值, 怎么办?

答: 因为要⼀步⼀步来, 先理解⼀下这个「左侧边界」 有什么特殊含义:

在这里插入图片描述

对于这个数组, 算法会返回 1。 这个 1 的含义可以这样解读:
nums 中⼩于 2的元素有 1 个。

⽐如对于有序数组 nums = [2,3,5,7], target = 1, 算法会返回 0, 含义是:
nums 中⼩于 1 的元素有 0 个。

再⽐如说 nums 不变, target = 8, 算法会返回 4, 含义是: nums 中⼩于 8 的元素有 4 个。

综上可以看出, 函数的返回值(即 left 变量的值) 取值区间是闭区间 [0,nums.length], 所以我们简单添加两⾏代码就能在正确的时候 return -1:

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

3、 为什么 left = mid + 1, right = mid ? 和之前的算法不⼀样?

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

4、 为什么该算法能够搜索左侧边界?

答: 关键在于对于

nums[mid] == target 这种情况的处理:
if (nums[mid] == target)
	right = mid;

可⻅, 找到 target 时不要⽴即返回, ⽽是缩⼩「搜索区间」 的上界 right, 在区间 [left, mid) 中继续搜索, 即不断向左收缩, 达到锁定左侧边界的⽬ 的。

5、 为什么返回 left ⽽不是 right?

答: 都是⼀样的, 因为 while 终⽌的条件是 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 if (nums[mid] > target) {
			right = mid;
		}
	}
	 return left - 1; // 注意
}

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

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

当 nums[mid] == target 时, 不要⽴即返回, ⽽是增⼤「搜索区间」 的下界left, 使得区间不断向右收缩, 达到锁定右侧边界的⽬的。

2、 为什么最后返回 left - 1 ⽽不像左侧边界的函数, 返回 left?
⽽且我觉得这⾥既然是搜索右侧边界, 应该返回 right 才对

答: ⾸先, while 循环的终⽌条件是 left == right, 所以 left 和 right 是⼀样的, 你⾮要体现右侧的特点, 返回 right - 1 好了。

⾄于为什么要减⼀, 这是搜索右侧边界的⼀个特殊点, 关键在这个条件判断:

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

在这里插入图片描述

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

3、 为什么没有返回 -1 的操作? 如果 nums 中不存在 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
所以决定了我们的「搜索区间」 是 [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, 必须减⼀
0

评论区