Binary Search Reexplained

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则是目标元素。

另外,强调两个细节:

  1. 注意后文中中点mid取值的小特点:使用left + (right - left) / 2来代替(left + right) / 2以避免直接加和溢出int(数比较小的时候就不用管了,但养成习惯最好)。
  2. 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也可以
}

参考

最后给出几个个人认为比较具有参考价值的链接:

  1. 左开右闭与左闭右闭区别/边界错误
    https://www.1point3acres.com/bbs/thread-432793-1-1.html