Notice: This article is only available in Chinese. :(
写在前面
二分虽然看起来没有几行,但真的算不上简单;细节方面陷阱很多.像我这种不拘小节的人,真的😖。
为此,我想系统地整理一下二分笔记。查了好一些资料,算法笔记、Segmentfault、知乎、博客园,有关二分查找的内容其实挺多的。然而大多数内容文字多形象表达少,算法全是语言描述,十分抽象,甚至不如直接上代码;这看得可真够累的,有那么麻烦吗?
我丢掉了大多数抽象而没必要的解释,整理了几个二分及变形的例程,写了这篇详细讨论常见的几种二分及变形算法的笔记。文中的例程均使用C。
为了清晰地观察算法的每一个动作,我定义了一个函数printStack()
,即本文的主角:
void printStack(int arr[], int n, int l, int m, int r, int s){
if (s) {
for (int i = 0; i < n; i ++) printf("%-4d", arr[i]);
printf("\n");
}
for (int i = 0; i < n; i ++) {
int j = 0;
char sign[4] = "";//初始化一个字符(比如说'.')作为placeholder
if (i == l) sign[j ++] = 'L';
if (i == m) sign[j ++] = 'm';
if (i == r) sign[j] = 'R';
printf("%-4s", sign);
}
printf("\n");
}
后文中二分函数均将printStack()
的调用注释掉了,实际测试时记得去掉注释。
然后统一说明后文二分查找函数的参数:n
为数列元素总个数(用于👆函数规范打印全部元素),arr[]
为已排序数列,left right
为查找区间左右边界,tar
则是目标元素。
另外,强调两个细节:
- 注意后文中中点
mid
取值的小特点:使用left + (right - left) / 2
来代替(left + right) / 2
以避免直接加和溢出int
(数比较小的时候就不用管了,但养成习惯最好)。 - C语言两数相除
\
是向下取舍,因此若两边界指针相连时,mid
取的是左边界。
各式各样的二分算法
1. 标准方法:
int bs_standard(int arr[], int n, int tar, int left, int right){
while (left <= right){
int mid = left + (right - left) / 2;
//printStack(arr, n, left, mid, right, 1);
if (arr[mid] == tar) return mid;
else if (arr[mid] > tar) right = mid - 1;
else left = mid + 1;
//printStack(arr, n, left, mid, right, 0);
}
return -1;
}
现在我们使用一个长度为15,已规范非递减排序,有重复元素的数组来测试;我们来看看输出:
共 19 项
左边界 0 右边界 17 目标元素值 3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
<- - - - ->
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
L m R
L R m
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
L m R
函数返回 3
这里用<- ->
箭头标定左右查找区域、L m R
分别表示三个左、中、右“指针”。(后同)
可以发现到这最后arr[m]==tar
,满足if
的条件,于是函数便返回了。
如果我们给出一个找不到的元素,看看算法又是怎么走的呢?
先给一个目标元素在区间之外靠右:
共 19 项
左边界 0 右边界 17 目标元素值 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
<- ->
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
Lm R
m LR
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
LmR
mR L
函数返回 -1
可以观察到左边界指针一心想着要出界,然后就出了😂。
而在区间范围内但不存在时,就会像这样:
共 18 项
左边界 0 右边界 17 目标元素值 4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
<- ->
0 1 2 3 3 3 5 6 7 8 9 10 11 12 13 13 13 13
L m R
L R m
0 1 2 3 3 3 5 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 5 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 5 6 7 8 9 10 11 12 13 13 13 13
Lm R
R Lm
函数返回 -1
这个标准二分应该来说是非常易懂了。因为while条件确定了查找区间是左右双闭区间[L, R]
。因此当左、右两个指针位置交叉后,查找停止。
标准二分既可以在while
退出后判断arr[m]==tar
,亦可在中途判断,满足条件时可立即结束。
因为这个方法左右向tar
推进的力度(姑且这么称呼叭)是对等的(基于同样的原因,将函数中的小于号改成大于号便可以对原数组的倒序数组进行查找),因此m
停下来的位置与起始时左右指针位置有关联,算法只管找到目标元素即停止,不能够找到相同元素的左右边界;于是我们来看看他的变形。
2. 标准方法变式(1) - 同元素左边界
这一次,我们让mid
指针所指元素与目标元素相同时函数不再返回(终止),而是将中点左边一位的元素下表赋值给右边界指针,然后继续。理所当然,如果目标元素有重复,右指针便是在向同元素左边界逼近,直到while
硬条件不满足为止。当然,没有重复元素就直接退出
搜索区间整体大致都向左边界靠近,我觉得这其实可以抽象出一个“质心”,然后“质心”向同元素左边界移动,直到大致重合(即m
只与L R
两个中的一个重合;而不完全重合才能使while
停下来)为止。
int bs_firstMatch(int arr[], int n, int tar, int left, int right){
while (left <= right){
int mid = left + (right - left) / 2;
//printStack(arr, n, left, mid, right, 1);
if (arr[mid] >= tar) right = mid - 1;
else left = mid + 1;
//printStack(arr, n, left, mid, right, 0);
}
return arr[left] == tar ? left : -1;
}
共 19 项
左边界 0 右边界 17 目标元素值 3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
<- - - - ->
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
L m R
L R m
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
L m R
L R m
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
L m R
m LR
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
LmR
mR L
函数返回 3
在区间范围内而又不存在时:
共 18 项
左边界 0 右边界 17 目标元素值 5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
<- ->
0 1 2 3 3 4 4 6 7 8 9 10 11 12 13 13 13 13
L m R
L R m
0 1 2 3 3 4 4 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 4 4 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 4 4 6 7 8 9 10 11 12 13 13 13 13
Lm R
m LR
0 1 2 3 3 4 4 6 7 8 9 10 11 12 13 13 13 13
LmR
R Lm
函数返回 -1
再来一个:
共 22 项
左边界 0 右边界 17 目标元素值 5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
<- ->
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
L R m
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
Lm R
m LR
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
LmR
mR L
函数返回 -1
从上述两个栗子还可以看出,函数返回时左指针指的元素是第一个大于目标值的元素。最后的return
怎么写,就因题而异了。
3. 标准方法变式(2) - 同元素右边界
道理大致也和同元素左边界查找函数相同啦,注意两者的区分即可
int bs_lastMatch(int arr[], int n, int tar, int left, int right){
while (left <= right){
int mid = left + (right - left) / 2;
printStack(arr, n, left, mid, right, 1);
if (arr[mid] > tar) right = mid - 1;
else left = mid + 1;
printStack(arr, n, left, mid, right, 0);
}
return arr[right] == tar ? right : -1;
}
直接来看🌰:
共 19 项
左边界 0 右边界 17 目标元素值 3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
<- - - - ->
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
L m R
L R m
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 5 6 7 8 9 10 11 12 13 13 13 13
Lm R
R Lm
函数返回 5
在区间范围内而不存在时:
共 22 项
左边界 0 右边界 17 目标元素值 5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
<- ->
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
L R m
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
Lm R
m LR
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
LmR
mR L
函数返回 -1
不知道你注意到了没有,两个变式在没找到元素时的退出状态是一致的(甚至步骤都是相同的),即函数返回时左指针指的元素是第一个大于目标值的元素。
这可不是巧合哦,因为这两个变式唯一的区别就在于arr[mid]==tar
时的动作。
同元素的区间范围内不存在,当元素在区间范围之外时,两变式也是一模一样的,这里不再放输出结果了。
4. C++标准库内置函数 - lowerbound
这个函数就稍微有一点麻烦了,先来看看吧:
int bs_stdLowerBound(int arr[], int n, int tar, int left, int right){
while (left < right){
int mid = left + (right - left) / 2;
//printStack(arr, n, left, mid, right, 1);
if (arr[mid] < tar) left = mid + 1;
else right = mid;
//printStack(arr, n, left, mid, right, 0);
}
return left;//与right相同
}
观察其与前三者的区别,最大者应该算是while
条件了吧。
前面说过,left<=right
确定了查找区间为左右双闭。而这里while
去掉了等号,再观察,查找区间为左闭右开区间,函数在两者相等时即可返回。
共 22 项
左边界 0 右边界 17 目标元素值 6
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
<- - - - - ->
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
L mR
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
Lm R
m LR
函数返回 8
再试试调整右边界后会有什么变化:
共 22 项
左边界 0 右边界 18 目标元素值 6
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
<- - - - - ->
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
L mR
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
m L R
0 1 2 3 3 3 4 4 6 6 6 6 7 8 9 10 11 12 13 13 13 13
Lm R
LmR
函数返回 8
5. c++标准库内置函数 - upperbound
其实前面有了下界函数,利用对称的思想很容易就写出上界函数了:
int bs_stdUpperBound(int arr[], int n, int tar, int left, int right){
while (left < right){
int mid = left + (right - left) / 2;
//printStack(arr, n, left, mid, right, 1);
if (arr[mid] > tar) right = mid - 1;
else left = mid;
//printStack(arr, n, left, mid, right, 0);
}
// return arr[left] == tar ? left : -1;
return left;//right也可以
}
共 25 项
左边界 0 右边界 21 目标元素值 4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
<- - - ->
0 1 2 3 3 3 4 4 6 6 6 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
L R m
0 1 2 3 3 3 4 4 6 6 6 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
Lm R
0 1 2 3 3 3 4 4 6 6 6 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
Lm R
0 1 2 3 3 3 4 4 6 6 6 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
Lm R
0 1 2 3 3 3 4 4 6 6 6 6 6 6 6 7 8 9 10 11 12 13 13 13 13
L m R
LR m
函数返回 7
测试源码
#include <stdio.h>
#define bsFunction bs_stdLowerBound
void printStack(int arr[], int n, int l, int m, int r, int s);
int bs_standard(int arr[], int n, int tar, int left, int right);
int binarySearch(int arr[], int n, int tar, int left, int right);
int bs_firstMatch(int arr[], int n, int tar, int left, int right);
int bs_lastMatch(int arr[], int n, int tar, int left, int right);
int bs_stdLowerBound(int arr[], int n, int tar, int left, int right);
int bs_stdUpperBound(int arr[], int n, int tar, int left, int right);
int main(){
int arr[] = {0, 1, 2, 3, 3, 3, 4, 4, 6, 6, 6, 6, 7, 8, 9, 10, 11, 12, 13, 13, 13, 13, 13}, n = sizeof(arr) / sizeof(int) - 1;
int tar = 26, left = 0, right = 20;
printf("共 %d 项\n左边界 %d 右边界 %d 目标元素值 %d\n\n", n, left, right, tar);
for (int i = 0; i < n; i ++) printf("%-4d", i);
printf("\n");
for (int i = 0; i < n; i ++) {
if (arr[i] == tar) printf("%-4s", "-");
else if (i == left) printf("%-4s", "<-");
else if (i == right) printf("%-4s", "->");
else printf("%-4c", ' ');
}
printf("\n");
printf("\n函数返回 %d \n", bsFunction(arr, n, tar, left, right));
return 0;
}
void printStack(int arr[], int n, int l, int m, int r, int s){
if (s) {
for (int i = 0; i < n; i ++) printf("%-4d", arr[i]);
printf("\n");
}
for (int i = 0; i < n; i ++) {
int j = 0;
char sign[4] = "";//初始化一个字符(比如说'.')作为placeholder
if (i == l) sign[j ++] = 'L';
if (i == m) sign[j ++] = 'm';
if (i == r) sign[j] = 'R';
printf("%-4s", sign);
}
printf("\n");
}
int binarySearch(int arr[], int n, int tar, int left, int right){
while (left < right){
int mid = left + (right - left) / 2;
printStack(arr, n, left, mid, right, 1);
if (arr[mid] >= tar) right = mid - 1;
else left = mid + 1;
printStack(arr, n, left, mid, right, 0);
}
return left;
}
int bs_standard(int arr[], int n, int tar, int left, int right){
while (left <= right){
int mid = left + (right - left) / 2;
printStack(arr, n, left, mid, right, 1);
if (arr[mid] == tar) return mid;
else if (arr[mid] > tar) right = mid - 1;
else left = mid + 1;
printStack(arr, n, left, mid, right, 0);
}
return -1;
}
int bs_firstMatch(int arr[], int n, int tar, int left, int right){
while (left <= right){
int mid = left + (right - left) / 2;
printStack(arr, n, left, mid, right, 1);
if (arr[mid] >= tar) right = mid - 1;
else left = mid + 1;
printStack(arr, n, left, mid, right, 0);
}
return arr[left] == tar ? left : -1;
}
int bs_lastMatch(int arr[], int n, int tar, int left, int right){
while (left <= right){
int mid = left + (right - left) / 2;
printStack(arr, n, left, mid, right, 1);
if (arr[mid] > tar) right = mid - 1;
else left = mid + 1;
printStack(arr, n, left, mid, right, 0);
}
return arr[right] == tar ? right : -1;
}
int bs_stdLowerBound(int arr[], int n, int tar, int left, int right){
while (left < right){
int mid = left + (right - left) / 2;
printStack(arr, n, left, mid, right, 1);
if (arr[mid] < tar) left = mid + 1;
else right = mid;
printStack(arr, n, left, mid, right, 0);
}
return arr[left] == tar ? left : -1;
// return left;//right也可以
}
int bs_stdUpperBound(int arr[], int n, int tar, int left, int right){
while (left < right){
int mid = left + (right - left) / 2;
printStack(arr, n, left, mid, right, 1);
if (arr[mid] > tar) right = mid - 1;
else left = mid;
printStack(arr, n, left, mid, right, 0);
}
// return arr[left] == tar ? left : -1;
return left;//right也可以
}
参考
最后给出几个个人认为比较具有参考价值的链接:
- 左开右闭与左闭右闭区别/边界错误
https://www.1point3acres.com/bbs/thread-432793-1-1.html