Binary Search Reexplained
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