赞
踩
「二分查找算法(Binary Search Algorithm)」:也叫做 「折半查找算法」、「对数查找算法」。是一种在有序数组中查找某一特定元素的搜索算法。
基本算法思想:先确定待查找元素所在的区间范围,在逐步缩小范围,直到找到元素或找不到该元素为止。
二分查找算法的过程如下所示:
举个例子来说,给定一个有序数组 [0, 1, 2, 3, 4, 5, 6, 7, 8]
。如果我们希望查找 5
是否在这个数组中。
[0, 1, 2, 3, 4, 5, 6, 7, 8]
,中位数是 4
,因为 4
小于 5
,所以如果 5
存在在这个数组中,那么 5
一定在 4
右边的这一半区间中。于是我们的查找范围变成了 [4, 5, 6, 7, 8]
。[4, 5, 6, 7, 8]
,中位数是 6
,因为 5
小于 6
,所以如果 5
存在在这个数组中,那么 5
一定在 6
左边的这一半区间中。于是我们的查找范围变成了 [4, 5, 6]
。[4, 5, 6]
,中位数是 5
,正好是我们需要查找的数字。于是我们发现,对于一个长度为 9
的有序数组,我们只进行了 3
次查找就找到了我们需要查找的数字。而如果是按顺序依次遍历数组,则最坏情况下,我们需要查找 9
次。
二分查找过程的示意图如下所示:
二分查找算法是经典的 「减而治之」 的思想。
这里的 「减」 是减少问题规模的意思,「治」 是解决问题的意思。「减」 和 「治」 结合起来的意思就是 「排除法解决问题」。即:每一次查找,排除掉一定不存在目标元素的区间,在剩下可能存在目标元素的区间中继续查找。
每一次通过一些条件判断,将待搜索的区间逐渐缩小,以达到「减少问题规模」的目的。而于问题的规模是有限的,经过有限次的查找,最终会查找到目标元素或者查找失败。
从上面的例子中我们了解了二分查找的思路和具体代码。但是真正在解决二分查找题目的时候还是需要考虑很多细节的。比如说以下几个问题:
mid
的取值问题:mid = (left + right) // 2
,还是 mid = (left + right + 1) // 2
?left <= right
,还是 left < right
?left = mid + 1
、right = mid - 1
、 left = mid
、right = mid
应该怎么写?下面一一进行讲解。
区间的左闭右闭、左闭右开指的是初始待查找区间的范围。
left = 0
,right = len(nums) - 1
,left
为数组第一个元素位置,right
为数组最后一个元素位置,从而区间 [left, right]
左右边界上的点都能取到。left = 0
,right = len(nums)
,left
为数组第一个元素位置,right
为数组最后一个元素的下一个位置,从而区间 [left, right)
左边界点能取到,而右边界上的点不能取到。关于区间的左闭右闭、左闭右开,其实在网上都有对应的代码和解法。但是相对来说,左闭右开这种写法在解决问题的过程中,需要考虑的情况更加复杂,所以建议 全部使用「左闭右闭」区间。
mid
的取值问题在二分查找的实际问题中,最常见的 mid
取值就是 mid = (left + right) // 2
或者 mid = left + (right - left) // 2
。前者是最常见写法,后者是为了防止整型溢出。式子中 // 2
就代表的含义是中间数「向下取整」。当待查找区间中有偶数个元素个数时,则位于最中间的数为 2
个,这时候使用上面式子只能取到中间靠左边那个数,而取不到中间靠右边的那个数。那么,右边的那个数到底能取吗?
其实,右边的数也是可以取的,令 mid = (left + right + 1) // 2
,或者 mid = left + (right - left + 1) // 2
。这样如果待查找区间的元素为偶数个,就能取到中间靠右边的那个数了,把这个式子代入到 704. 二分查找 中试一试,发现也是能通过题目评测的。
这是因为二分查找的思路是根据每次选择中间位置上的数值来决定下一次在哪个区间查找元素。每一次选择的元素位置可以是中间位置,但并不是一定非得是区间中间位置元素,靠左一些、靠右一些、甚至区间三分之一、五分之一处等等,都是可以的。比如说 mid = left + (right - left + 1) * 1 // 5
也是可以的。
但一般来说,取中间位置元素在平均意义下所达到的效果最好。同时这样写最简单。而对于 mid
值是向下取整还是向上取整,大多数时候是选择不加 1
。但有些写法中,是需要考虑加 1
的,后面会讲解这种写法。
我们经常看到二分查找算法的写法中,while
语句出界判断的语句有left <= right
和 left < right
两种写法。那我们究竟应该在什么情况用什么写法呢?
这就需要判断一下导致 while
语句出界的条件是什么。
left <= right
,且查找的元素不存在,则 while
判断语句出界条件是 left == right + 1
,写成区间形式就是 [right + 1, right]
,此时待查找区间为空,待查找区间中没有元素存在,所以此时终止循环可以直接返回 -1
是正确的。
[3, 2]
,不可能存在一个元素既大于等于 3
又小于等于 2
,此时直接终止循环,返回 -1
即可。left < right
,且查找的元素不存在,则 while
判断语句出界条件是 left == right
,写成区间形式就是 [right, right]
。此时区间不为空,待查找区间还有一个元素存在,并不能确定查找的元素不在这个区间中,此时终止循环返回 -1
是错误的。
[2, 2]
,元素 2
就属于这个区间,此时终止循环,返回 -1
就漏掉了这个元素。但是如果我们还是想要使用 left < right
的话,怎么办?
可以在返回的时候需要增加一层判断,判断 left
所指向位置是否等于目标元素,如果是的话就返回 left
,如果不是的话返回 -1
。即:
// ...
while (left < right) {
// ...
}
return nums[left] == target ? left : -1;
此外,循环语句用 left < right
还有一个好处,就是在退出循环的时候,一定有 left == right
,我们就不用判断应该返回 left
还是 right
了。
在进行区间范围选择的时候,有时候是 left = mid + 1
、right = mid - 1
,还有的时候是 left = mid + 1
、right = mid
,还有的时候是 left = mid
、right = mid - 1
。那么我们到底应该如何确定搜索区间范围呢?
这是二分查找的一个难点,写错了很容易造成死循环,或者得不到正确结果。
这其实跟二分查找算法的两种不同思路有关。
思路 1:「直接找」
第 1 种思路:一旦我们在循环体中找到元素就直接返回结果。
这种思路比较简单,其实我们在上边 「3. 简单二分查找 - 704. 二分查找」 中就已经用过了。这里再看一下思路和代码:
思路:
取两个节点中心位置 mid
,先看中心位置值 nums[mid]
。
nums[mid]
与目标值 target
相等,则 直接返回 这个中心位置元素的下标。nums[mid]
小于目标值 target
,则将左节点设置为 mid + 1
,然后继续在右区间 [mid + 1, right]
搜索。nums[mid]
大于目标值 target
,则将右节点设置为 mid - 1
,然后继续在左区间 [left, mid - 1]
搜索。int binarySearch(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
细节:
left <= right
。思路 2:「排除法」
第 2 种思路:在循环体中排除目标元素一定不存在区间。
思路:
mid
,根据判断条件先将目标元素一定不存在的区间排除。根据第二种排除法的思路,我们可以写出来两种代码。
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
//寻找左边界
//找到 ≥target的最小值
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
// 在区间 [left, right] 内查找 target
while (left < right) {
// 取区间中间节点
int mid = left + (right - left) / 2;
// nums[mid] 小于目标值,排除掉不可能区间 [left, mid],在 [mid + 1, right] 中继续搜索
if (nums[mid] < target) {
left = mid + 1;
// nums[mid] 大于等于目标值,目标元素可能在 [left, mid] 中,在 [left, mid] 中继续搜索
} else {
right = mid;
}
}
// 判断区间剩余元素是否为目标元素,不是则返回 -1
return nums[left] == target ? left : -1;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
//寻找右边界
//找到 ≤target 的最大值
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
// 在区间 [left, right] 内查找 target
while (left < right) {
// 取区间中间节点
int mid = left + (right - left + 1) / 2;
// nums[mid] 大于目标值,排除掉不可能区间 [mid, right],在 [left, mid - 1] 中继续搜索
if (nums[mid] > target) {
right = mid - 1;
// nums[mid] 小于等于目标值,目标元素可能在 [mid, right] 中,在 [mid, right] 中继续搜索
} else {
left = mid;
}
}
// 判断区间剩余元素是否为目标元素,不是则返回 -1
return nums[left] == target ? left : -1;
}
细节:
left < right
。这样在退出循环时,一定有left == right
成立,就不用判断应该返回 left
还是 right
了。同时方便定位查找元素的下标。但是一定要注意最后要对区间剩余的元素进行一次判断。nums[mid]
在什么情况下一定不是目标元素,排除掉不可能区间,然后再从剩余区间中确定下一次查找区间的范围。nums[mid]
在什么情况下一定不是目标元素之后,它的对立面(即 else
部分)一般就不需要再考虑区间范围了,直接取上一个区间的反面区间。如果上一个区间是 [mid + 1, right]
,那么相反面就是 [left, mid]
。如果上一个区间是 [left, mid - 1]
,那么相反面就是 [mid, right]
。[left, mid - 1]
与 [mid, right]
两部分时,mid
取值要向上取整。即 mid = left + (right - left + 1) // 2
。因为如果当区间中只剩下两个元素时(此时 right = left + 1
),一旦进入 left = mid
分支,区间就不会再缩小了,下一次循环的查找区间还是 [left, right]
,就陷入了死循环。left = mid
就向上取整。或者记为:
left = mid + 1
、right = mid
和 mid = left + (right - left) /2
一定是配对出现的。right = mid - 1
、left = mid
和 mid = left + (right - left + 1) / 2
一定是配对出现的。left <= right
,有时候要考虑返回是 left
还是 right
。循环体内有 3 个分支,并且一定有一个分支用于退出循环或者直接返回。这种思路适合解决简单题目。即要查找的元素性质简单,数组中都是非重复元素,且 ==
、>
、<
的情况非常好写的时候。给定一个按照升序排列的长度为n的整数数组,以及 q 个查询。对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。如果数组中不存在该元素,则返回“-1 -1”。
输入格式
输出格式
数据范围
输入样例
6 3
1 2 2 3 3 4
3
4
5
输出样例
3 4
5 5
-1 -1
题解思路
这道题可以使用二分查找来解决。我们首先实现两个二分查找函数,一个用于找到元素k的起始位置,另一个用于找到元素k的终止位置。然后,对于每个查询,我们使用这两个函数分别找到起始位置和终止位置,并输出结果。
参考代码
#include<iostream>
using namespace std;
int n, q;
const int N = 100010;
int a[N];
int binary_search(int k) {
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (a[mid] < k) l = mid + 1;
else r = mid;
}
return l;
}
int binary_search2(int k) {
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (a[mid] > k) r = mid - 1;
else l = mid;
}
return l;
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
while (q--) {
int temp;
scanf("%d", &temp);
int p = binary_search(temp);
int q = binary_search2(temp);
if (a[p] == temp)
cout << p << " " << q << endl;
else cout << "-1 -1" << endl;
}
return 0;
}
这样,我们就完成了对这道题目的解答。通过这个例子,我们可以看到二分查找在处理有序数组时的应用,以及如何利用二分查找来解决一些问题。
需要注意的是,不存在 target
的时候,直接返回 -1
。在二分查找值时,返回条件是 nums[mid] == target
时直接 return
,而查找左右侧边界时,返回条件则需要等 while()
循环完毕后,才能返回。观察下表可知,区间右侧开闭主要影响 right
的更新和 while
判断。
场景 | 左闭右开 [left, right) | 左闭右闭 [left, right] | 备注 |
---|---|---|---|
初始赋值 | left = 0 , right = numsSize | left = 0 , right = numsSize - 1 | 部分不同 |
while条件 | left < right | left <= right | 不同 |
nums[mid] < target | left = mid + 1 | left = mid + 1 | 相同 |
nums[mid] > target | right = mid | right = mid - 1 | 不同 |
nums[mid] == target | 返回 mid | 返回 mid | 相同 |
下面左右侧边界查找采用的是左闭右开区间,读者有兴趣可自行分析左闭右闭区间对应的情况。注意,如果有左边界不存在的场景,在 while
循环后,要判断下标对应值是否与 target
相等。
观察下表可知,在区间开闭情况相同时,左右侧边界的查找的主要区别在于 nums[mid] == target
时边界更新和返回值。
场景 | 左侧边界 | 右侧边界 | 备注 |
---|---|---|---|
初始赋值 | left = 0 , right = numsSize | left = 0 , right = numsSize | 相同 |
while条件 | left < right | left < right | 相同 |
nums[mid] < target | left = mid + 1 | left = mid + 1 | 相同 |
nums[mid] > target | right = mid | right = mid | 相同 |
nums[mid] == target | right = mid | left = mid + 1 | 不同 |
返回值 | left | left - 1 | 不同 |
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。