Algo: Binary search

二分查找的基本写法：

#include <vector>
#include <iostream>

int binarySearch(std::vector<int> coll, int key)
{
    int l = 0;
    int r = (int)coll.size() - 1;

    while (l <= r)
    {
        int m = l + (r - l) / 2;
 
        if (key == coll[m])
        {
            return m;
        }

        if (key > coll[m])
        {
            l = m + 1;
        }
        else
        {
            r = m - 1;
        }
    }

    return -1;
}
int main()
{
    int arr[] = { 2, 3, 4, 10, 40 };
    std::vector<int> coll(arr, arr + sizeof(arr) / sizeof(arr[0]));
    
    int key = 10;
    int index = binarySearch(coll, key);

    if (-1 == index)
    {
        std::cout << "Element is not present in array" << std::endl;
    }
    else
    {
        std::cout << "Element is present at index " << index << std::endl;
    }

    return 0;
}

历史上，Knuth在其<<Sorting and Searching>>一书的第6.2.1节指出：尽管第一个二分搜索算法于1946年就出现，然而第一个完全正确的二分搜索算法直到1962年才出现。

而不经仔细斟酌而写出的一个二分查找经常遭遇off by one或者无限循环的错误。下面将讨论二分查找的理论基础，实现应用，及如何采用何种技术保证写出一个正确的二分程序，让我们免于思考麻烦的边界及结束判断问题。

在C++的STL中有如下函数 lower_bound、upper_bound、binary_search、equal_range，这些函数就是我们要考虑如何实现的那些。通过实现这些函数，可以检查你是否真的掌握了二分查找。

理论基础：
当我们碰到一个问题，需要判断它是否可以采用二分查找来解决。对于最一般的数的查找问题，这点很容易判断，然而对于某些比如可以采用二分+贪心组合，二分解方程，即某些具有单调性的函数问题，也是可以利用二分解决的，然而有时它们表现的不那么显然。

考虑一个定义在有序集合S上的断言，搜索空间内包含了问题的候选解。在本文中，一个断言实际上是一个返回布尔值的二值函数。这个断言可以用来验证一个候选解是否是所定义的问题合法的候选解。

我们把下面的一条定理称之为Main Theorem: Binary search can be used if and only if for all x in S, p(x) implies p(y) for all y > x. 实际上通过这个属性，我们可以将搜索空间减半，也就是说如果我们的问题的解应用这样的一个验证函数，验证函数的值可以满足上述条件，这样这个问题就可以用二分查找的方法来找到那个合适的解，比如最左侧的那个合法解。以上定理还有一个等价的说法 !p(x) implies !p(y) for all y < x 。这个定理很容易证明，这里省略证明。

实际上如果把这样的一个p函数应用于整个序列，我们可以得到如下的一个序列
fasle false false ......true true....
如果用01表示，实际上就是如下这样的一个序列0 0 0 0......1 1 1 1.......
而所有的二分查找问题实际都可以转化为这样的一个01序列中第一个1的查找问题，实际上我们就为二分查找找到了一个统一的模型。就像排序网络中利用的01定理，如果可以对所有的01序列排序，则可以为所有的序列排序。实际上二分查找也可以用来解决true true....fasle false false ......即1 1 1 1...... 0 0 0 0.....序列的查找问题。当然实际如果我们把p的定义变反，这个序列就变成了上面的那个，也就是可以转化为上面的模型。

这样我们就把所有问题转化为求0011模式序列中第一个1出现的位置。当然实际中的问题，也可能是求1100模式序列最后一个1的位置。同时要注意对应这两种情况下的实现有些许不同，而这个不同对于程序的正确性是很关键的。

下面的例子对这两种情况都有涉及，一般来说具有最大化要求的某些问题，它们的断言函数往往具有1100模式，比如poj3258 River Hopscotch；而具有最小化要求的某些问题，它们的断言函数往往具有0011模式，比如poj3273 Monthly Expense。

而对于数key的查找，我们可以利用如下一个断言使它成为上述模式。比如x是否大于等于key，这样对于一个上升序列来说它的断言函数值成为如下模式：0 0 0 0......1 1 1 1.......，而寻找最左边的key(类似stl中的lower_bound,则就是上述模型中寻找最左边的1.当然问题是寻找最后出现的那个key(类似stl中的upper_bound),只需要把断言修改成：x是否小于等于key，就变成了1 1 1 1...... 0 0 0 0.....序列的查找问题。

可见这样的查找问题，变成了如何寻找上述序列中的最左或最右的1的问题。

类似的一个单调函数的解的问题，只要设立一个断言：函数值是否大于等于0？也变成了如上的序列，如果是单调上升的，则变成了0011模式，反之则是1100模式。实际上当函数的自变量取值为实数时，这样的一个序列实际上变成了一种无穷数列的形式，也就是1111.....0000中间是无穷的，01的边界是无限小的。这样寻找最右侧的1，一般是寻找一个近似者，也就是采用对实数域上的二分(下面的源代码4)，而用fabs(begin-end)来控制精度，确定是否停止迭代。比如poj 3122就是在具有1111.....0000模式的无穷序列中查找那个最右侧的1，对应的自变量值。

基本例题

poj 3233 3497 2104 2413 3273 3258 1905 3122

注：

poj1905 实际上解一个超越方程 L"sinx -Lx=0,可以利用源码4，二分解方程

poj3258 寻找最大的可行距离，实际上是111000序列中寻找最右侧的1，可以参考源码3

poj3273 寻找最小的可行值，实际上是000111序列中寻找最左侧的1，可以参考源码2

总结

1、首先寻找进行二分查找的依据，即符合main 理论的一个断言：0 0 0 ........111.......

2、确定二分的上下界，尽量的让上下界松弛，防止漏掉合理的范围，确定上界，也可以倍增法

3、观察确定该问题属于0011还是1100模式的查找

4、写程序注意两个不变性的保持

5、注意验证程序可以处理01这种两个序列的用例，不会出错

6、注意mid = begin+(end-begin)/2,用mid=(begin+end)/2是有溢出危险的。实际上早期的java的jdk里的二分搜索就有这样的bug，后来java大师Joshua Bloch发现，才改正的。

对二分查找进行分类：取整方式：向下取整向上取整（共2种）区间开闭：闭区间左闭右开区间左开右闭区间开区间（共4种）问题类型：对于不下降序列a，求最小的i，使得a[i] = key对于不下降序列a，求最大的i，使得a[i] = key对于不下降序列a，求最小的i，使得a[i] > key对于不下降序列a，求最大的i，使得a[i] < key对于不上升序列a，求最小的i，使得a[i] = key对于不上升序列a，求最大的i，使得a[i] = key对于不上升序列a，求最小的i，使得a[i] < key对于不上升序列a，求最大的i，使得a[i] > key（共8种）综上所述，二分查找共有2*4*8=64种写法。

重要的是要会写一种对的。

首先有几个数字要注意

1、中位数有两个：
下位中位数：lowerMedian = (length - 2) / 2;
上位中位数：upperMedian = length / 2;
常用的是下位中位数，通用的写法如下，语言int经常自动向下取整，

median = (length - 1) / 2;
指针的区间当然可以开区间，也可以闭区间，也可以半开半闭。但老老实实两头取闭区间总是不会错。上面的中位数，转换成两头闭区间 [low,high] 就变成下面这样：

median = low + (high - low) / 2;

2、不要图快用加法，会溢出，
median = ( low + high ) / 2; // OVERFLOW

3、另外一个关键点是“终结条件”

不要以 low == high 做终结条件，会被跳过的。

if (low == high)
{
    return (nums[low] >= target)? low : ++low;
}

不相信在 [1, 5] 里找 0 试试？

正确的终结条件是：

low > high
也就是搜索空间为空。

满足终结条件以后，返回值完全不需要纠结，直接返回低位 low。

因为回过头去放慢镜头，二分查找的过程就是一个维护 low 的过程：
low从0起始。只在中位数遇到确定小于目标数时才前进，并且永不后退。low一直在朝着第一个目标数的位置在逼近。知道最终到达。
至于高位 high，就放心大胆地缩小目标数组的空间吧。

所以最后的代码非常简单，

#include <vector>
#include <iostream>

int binarySearch(std::vector<int> coll, int key)
{
    int low = 0;
    int high = (int)coll.size() - 1;

    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (key > coll[mid])
        {
            low = mid + 1;
        }
        else if (key < coll[mid])
        {
            high = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    
    return low;
}
 
int main()
{
    int arr[] = { 2, 3, 4, 10, 40 };
    std::vector<int> coll(arr, arr + sizeof(arr) / sizeof(arr[0]));
    
    int key = 10;
    int index = binarySearch(coll, key);

    if (-1 == index)
    {
        std::cout << "Element is not present in array" << std::endl;
    }
    else
    {
        std::cout << "Element is present at index " << index << std::endl;
    }

    return 0;
}

递归版也一样简单，

#include <vector>
#include <iostream>

int binarySearchRecur(std::vector<int> coll, int key, int low, int high)
{
    if (low > high)
    {
        return low;
    }

    int mid = low + (high - low) / 2;
    if (key > coll[mid])
    {
        return binarySearchRecur(coll, key, mid + 1, high);
    }
    else if (key < coll[mid])
    {
        return binarySearchRecur(coll, key, low, mid - 1);
    }
    else
    {
        return mid;
    }
}

int main()
{
    int arr[] = { 2, 3, 4, 10, 40 };
    std::vector<int> coll(arr, arr + sizeof(arr) / sizeof(arr[0]));
    int size = (int)coll.size();

    int key = 10;
    int index = binarySearchRecur(coll, key, 0, size);

    if (-1 == index)
    {
        std::cout << "Element is not present in array" << std::endl;
    }
    else
    {
        std::cout << "Element is present at index " << index << std::endl;
    }

    return 0;
}

但上面的代码能正常工作，有一个前提条件：元素空间没有重复值。

推广到有重复元素的空间，二分查找问题就变成：
寻找元素第一次出现的位置。
也可以变相理解成另一个问题，对应C++的 lower_bound() 函数，寻找第一个大于等于目标值的元素位置。

但只要掌握了上面说的二分查找的心法，代码反而更简单：

#include <vector>
#include <iostream>

int binarySearch(std::vector<int> coll, int key)
{
    int low = 0;
    int high = (int)coll.size() - 1;

    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (key > coll[mid])
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    
    return low;
}
 
int main()
{
    int arr[] = { 2, 3, 4, 10, 40 };
    std::vector<int> coll(arr, arr + sizeof(arr) / sizeof(arr[0]));
    
    int key = 10;
    int index = binarySearch(coll, key);

    if (-1 == index)
    {
        std::cout << "Element is not present in array" << std::endl;
    }
    else
    {
        std::cout << "Element is present at index " << index << std::endl;
    }

    return 0;
}

翻译成递归版也是一样：

#include <vector>
#include <iostream>

int binarySearchRecur(std::vector<int> coll, int key, int low, int high)
{
    if (low > high)
    {
        return low;
    }

    int mid = low + (high - low) / 2;
    if (key > coll[mid])
    {
        return binarySearchRecur(coll, key, mid + 1, high);
    }
    else
    {
        return binarySearchRecur(coll, key, low, mid - 1);
    }
}

int main()
{
    int arr[] = { 2, 3, 4, 10, 40 };
    std::vector<int> coll(arr, arr + sizeof(arr) / sizeof(arr[0]));
    int size = (int)coll.size();

    int key = 10;
    int index = binarySearchRecur(coll, key, 0, size);

    if (-1 == index)
    {
        std::cout << "Element is not present in array" << std::endl;
    }
    else
    {
        std::cout << "Element is present at index " << index << std::endl;
    }

    return 0;
}

以上代码均通过leetcode测试。标准银弹。每天早起写一遍，锻炼肌肉。

最后想说，不要怕二分查找难写，边界情况复杂。实际情况是，你觉得烦躁，大牛也曾经因为这些烦躁过。一些臭名昭著的问题下面，经常是各种大牛的评论（恶心，变态，F***，等等）。而且这并不考验什么逻辑能力，只是仔细的推演罢了。拿个笔出来写一写，算一算不丢人。很多问题彻底搞清楚以后，经常就是豁然开朗，然后以后妥妥举一反三。以上。

参考：

https://www.zhihu.com/question/36132386
https://en.wikipedia.org/wiki/Binary_search_algorithm
https://www.geeksforgeeks.org/binary-search/
https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/

Algo: Binary search

相关推荐