二分算法详解（马智颖）

[Mzying2001]

二分算法详解

如果看不到图片，看这里：点击跳转

本文详细讲解了二分算法的相关内容，但也不局限于讲二分法，文章后面还会介绍与二分算法相似的算法，如插值查找算法，斐波那契查找算法、三分算法等。

目录：

• 二分算法详解
  • 算法简介
  • 算法思路
  • 时间复杂度
  • 代码示例
    • 递归版本
    • 非递归版本
    • 注意事项
  • 二分法假定解
    • 结束条件
  • 二分算法的应用
    • 例题1、求平方根
    • 例题2、猜数字大小
    • 例题3、搜索旋转排序数组
    • 例题4、Cable master（POJ - 1064）
  • 发现问题
    • 暴力解法
    • 缓存结果
    • 寻找左侧边界的二分搜索
    • 寻找右侧边界的二分搜索
  • 算法变式
    • 插值查找算法
    • 斐波那契查找算法（黄金分割法）
  • 三分算法
  • 参考资料

算法简介

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，前提是数据结构必须先排好序，可以在数据规模的对数时间复杂度内完成查找。但是，二分查找要求线性表具有有随机访问的特点（例如数组），也要求线性表能够根据中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果。

算法思路

1. 首先确定数组的中间值的下标 mid = (left + right) / 2
2. 将要查找的数 target 和 arr[mid] 做比较
   • 若 target > arr[mid]，说明要查找的数在 mid 的右边，因此需要向右查找
   • 若 target < arr[mid]，说明要查找的数在 mid 的左边，因此需要向左查找
   • 若 target == arr[mid]，说明已经找到要找到值，此时 mid 就是目标值的下标，返回 mid
3. 重复以上步骤，直到找到；若最后出现 left > right，说明在数组中不存在要找的值，就返回-1

下图为运用二分算法在数组 [1, 3, 4, 6, 7, 8, 10, 13, 14] 中查找数字 4 的过程图解。

图片来源：百度百科

时间复杂度

由于二分查找每一次都会排除掉一半的值，在最坏的情况下即排除到最后只剩一个值，即 2^m=n，所以其时间复杂度为 log2(n)，即对数阶 O(logn)。

代码示例

以下以 std::vector 为例，数组的话传个length参数就行了。

递归版本

int binarySearch(std::vector<int> &nums, int left, int right, int target)
{
    //找不到，返回-1
    if (left > right)
        return -1;

    //防止(left + right)溢出
    int mid = left + (right - left) / 2;

    if (nums[mid] == target)
    {
        //找到target，返回下标
        return mid;
    }
    else if (nums[mid] < target)
    {
        //中间的值小于target，说明target在右边
        return binarySearch(nums, mid + 1, right, target);
    }
    else
    {
        //中间的值大于target，说明target在左边
        return binarySearch(nums, left, mid - 1, target);
    }
}

//重载binarySearch方法，便于调用
int binarySearch(std::vector<int> &nums, int target)
{
    //nums为空则直接返回-1，否则递归查找
    return nums.size() == 0 ? -1 : binarySearch(nums, 0, nums.size() - 1, target);
}

非递归版本

int binarySearch(std::vector<int> &nums, int target)
{
    //nums为空时直接返回-1
    if (nums.size() == 0)
        return -1;

    int left = 0;
    int right = nums.size() - 1;

    while (left <= right)
    {
        //防止(left + right)溢出
        int mid = left + (right - left) / 2;

        if (nums[mid] == target)
        {
            //找到target，返回下标
            return mid;
        }
        else if (nums[mid] < target)
        {
            //中间的值小于target，说明target在右边
            left = mid + 1;
        }
        else
        {
            //中间的值大于target，说明target在左边
            right = mid - 1;
        }
    }
    //找不到，返回-1
    return -1;
}

注意事项

二分算法的思路和代码很简单，基本上没什么好讲的，最可能出错的点就是循环条件 left <= right，注意是 <=，而不是 <，原因也很好理解，举个例子就知道了：

比如我要通过二分查找数组 [1, 2] 中的 2，很明显，第一次循环后 left 和 right 都是1，即都指向数组中的第二个值 2，此时显然还不能跳出循环，因为此时计算出 mid 也是1，所指向的就是要找的数，应返回 mid 而不是直接返回-1，由此则可以看出应该是 <=，而不是 <。

还有一个点就是 mid 的计算方式，最直接的就是 mid = (left + right) / 2，但这样有一定的风险，就是当 left 和 right 很大时，直接相加有可能会溢出，即超出int的范围，在上面的代码中 mid = left + (right - left) / 2 就可以避免这种情况，虽然这种情况大多数时候是不会出现的，但这样写保险点。

二分法假定解

前面讲得是最简单的二分搜索，但大多数题目可不会这么简单，二分法还有一个很重要的方法，就是运用二查找假定一个解并判断是否可行。一个简单的应用就是知道函数值求自变量的值，假设有一个单调增函数 f(x)，现在要在区间 [left, right] 上求出函数值 y 对应的 x，运用二分的思想，我们可以前定义让 mid = (left + right) / 2，假设它就是要求的x，先求出 f(mid)，与 y 比较，若 f(mid) < y，说明 mid 的值取小了，那么就让 left = mid；同样，若 f(mid)>y 则应是 right = mid，通过这样逐步缩减区间 [left, right]，当 left 和 right 相差很小时就可以近似地认为这个 left 或者 right 就是要求的 x。

代码示例：

double f(double x)
{
    return x * x * x; //以y=x^3为例
}

double get(double y)
{
    double left = 0;
    double right = 1E10;

    //二分100次，使区间足够小
    for (int i = 0; i < 100; i++)
    {
        double mid = (left + right) / 2;

        if (f(mid) < y)
            left = mid;
        else
            right = mid;
    }

    return left;
}

/*
    输入：2
    输出：1.25992

    输入：5
    输出：1.70998
*/

结束条件

循环结束的条件就是 left 和 right 很接近，达到精度要求。那么就有以下两种思路：

//思路1：
while (right - left > 精度) { ... }

//思路2：
for (int i = 0; i < 循环次数; i++) { ... }

以上两种均可达到目的，但如果使用思路1，有可能由于浮点数精度的问题导致死循环。

二分算法的应用

例题1、求平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1：

输入: 4
输出: 2

示例 2：

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

代码如下：

class Solution
{
public:
    int mySqrt(int x)
    {
        if (x == 0 || x == 1)
            return x;

        int left = 0;
        int right = x;

        int mid, tmp;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            tmp = x / mid;

            if (tmp == mid)
                return mid;
            else if (tmp < mid)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return right;
    }
};

题目来源：LeetCode

---

例题2、猜数字大小

猜数字游戏的规则如下：

• 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
• 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
• 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
  • -1：我选出的数字比你猜的数字小 pick < num
  • 1：我选出的数字比你猜的数字大 pick > num
  • 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

示例 1：

输入：n = 10, pick = 6
输出：6

示例 2：

输入：n = 1, pick = 1
输出：1

示例 3：

输入：n = 2, pick = 1
输出：1

示例 4：

输入：n = 2, pick = 2
输出：2

提示：

• 1 <= n <= 2^31 - 1
• 1 <= pick <= n

代码如下：

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return       -1 if num is lower than the guess number
 *                1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

class Solution
{
public:
    int guessNumber(int n)
    {
        int left = 1;
        int right = n;

        int mid;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            switch (guess(mid))
            {
            case 0:
                return mid;

            case 1:
                left = mid + 1;
                break;

            case -1:
                right = mid - 1;
                break;
            }
        }
        return -1;
    }
};

题目来源：LeetCode

---

例题3、搜索旋转排序数组

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• nums 肯定会在某个点上旋转
• -10^4 <= target <= 10^4

代码如下：

class Solution
{
public:
    int search(std::vector<int> &nums, int target)
    {
        if (nums.size() == 0)
            return -1;

        int left = 0;
        int right = nums.size() - 1;

        int mid;
        while (left <= right)
        {
            mid = left + (right - left) / 2;

            if (nums[mid] == target)
                return mid;

            if (nums[mid] < nums[left])
            {
                //右侧有序
                if (nums[right] == target)
                    return right;

                if (nums[mid] < target && target < nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            else
            {
                //左侧有序
                if (nums[left] == target)
                    return left;

                if (nums[mid] > target && target > nums[left])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
        }
        return -1;
    }
};

题目来源：LeetCode

---

例题4、Cable master（POJ - 1064）

李老板要求光头强在周日送K根长度相同的木头到公司。光头强的仓库里有N根长度不等的木头，因此，光头强需要进行切割，并把长度相同的K根木头送到公司（本题当中的给出的木头长度单位是米，光头强的切割技术只能精确到厘米，也就是说答案保留到小数点后两位小数），同时光头强为了向李老板表示自己非常的勤劳没有偷懒，决定让这K根木头的长度达到最大，你能告诉她这K根木头最大的长度是多少吗？（PS:木头不允许拼接，要不然李老板要扣工资的！）

Input

第一行给出n和K，分别代表光头强库存木头的数目和李老板要求的木头的数目；（1<=N,k<=10000） 接下来N行分别给出光头强N根木头的长度，木头长度在int范围内

Output

输出木头的最大长度，结果保留两位小数

Sample Input

4 11
8.02
7.43
4.57
5.39

Sample Output

2.00

代码如下：

#include <iostream>
#include <cmath>
#include <algorithm>

const int int32_max = ~(1 << 31);

bool check(double *lens, int n, int k, double mid)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += std::floor(lens[i] / mid);
    return sum >= k;
}

int main()
{
    using namespace std;
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n, k;
    while (cin >> n >> k)
    {
        double *lens = new double[n];

        for (int i = 0; i < n; i++)
            cin >> lens[i];

        double left = 0;
        double right = int32_max;

        for (int i = 0; i < 100; i++)
        {
            double mid = (left + right) / 2;

            if (check(lens, n, k, mid))
                left = mid;
            else
                right = mid;
        }

        printf("%.2lf\n", floor(right * 100) / 100);

        delete[] lens;
    }

    return 0;
}

题目来源：POJ - 1064

发现问题

尽管上面的二分算法大部分能够满足我们的要求，但是当数组中有重复的元素时（注意看看前面的几道题都是没有重复的元素），返回值就不一定是我们想要的。

举个例子，当 arr = [0, 1, 1, 1, 2]，target = 1 时通过以上的代码所返回的值是 2，但是在数组中下标为1、2、3的都是1，有时候我们需要拿到第一个出现的元素下标，亦或者是最后一个，那么前面的算法就明显不满足要求。

暴力解法

最直接的解决方法就是在找到值后，让后再向左向右线性搜索，代码如下：

int binarySearch(std::vector<int> &nums, int target)
{
    if (nums.size() == 0)
        return -1;

    int left = 0;
    int right = nums.size() - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target)
        {
            /*由于nums是排好序的，因此相同的元素都排在一起*/

            //向左寻找
            while (mid - 1 >= 0 && nums[mid - 1] == target)
                mid--;

            // //向右寻找
            // while (mid + 1 >= 0 && nums[mid + 1] == target)
            //     mid++;

            return mid;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return -1;
}

以上代码就解决了前面的问题，但是很明显，这样写存在一个很大的问题：数组中间可能有很多个与要找的数相等的元素，这样做就无法保证二分查找对数级的时间复杂度了。

缓存结果

实际上，只要在原来代码的基础上加一个变量 ans 来缓存结果就行了，代码如下：

int binarySearch(std::vector<int> &nums, int target)
{
    if (nums.size() == 0)
        return -1;

    int left = 0;
    int right = nums.size() - 1;

    int mid, ans = -1;
    while (left <= right)
    {
        mid = left + (right - left) / 2;

        if (nums[mid] == target)
        {
            ans = mid;

            //向左
            right = mid - 1;

            // //向右
            // left = mid + 1;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return ans;
}

这种方法很好理解，在找到 target 后没有立即返回下标，而是将结果存放在变量 ans 中，然后继续进行二分，直到二分完整个数组。

下面，我再介绍另外一种实现方法。

寻找左侧边界的二分搜索

代码如下：

int binarySearch(std::vector<int> &nums, int target)
{
    if (nums.size() == 0)
        return -1;

    int left = 0;
    int right = nums.size(); //注意不用-1

    while (left < right) //注意不是<=
    {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target)
        {
            right = mid; //找到，继续向左二分
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }

    if (left == nums.size() || nums[left] != target)
        return -1;
    else
        return left;
}

这种方法其实也很好理解，可以类比前一种做法，这个其实就是直接用变量 right 来保存结果。

由于 right 要用来保存结果，二分搜索的区间不应该包括这个 right，即只在区间 [left, right - 1] 上进行二分搜索，因此循环条件就是 left < right 而不是 left <= right，当找到目标元素时，就让 right 指向这个元素，继续向左进行二分搜索。在二分完整个数组后就只需要判断 right 指向的元素是否为想要找到的元素就行了。

寻找右侧边界的二分搜索

代码如下：

int binarySearch(std::vector<int> &nums, int target)
{
    if (nums.size() == 0)
        return -1;

    int left = 0;
    int right = nums.size();

    while (left < right)
    {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target)
        {
            left = mid + 1;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }

    if (left == 0 || nums[left - 1] != target)
        return -1;
    else
        return left - 1;
}

思路和前面一个是一样的，这里就不再赘述了。

算法变式

插值查找算法

不要去看插值查找这个名字，实际上它的思想跟二分查找算法基本一样，只是对于中间值的获取策略不同而已。

在有序数组中查找值时，由于数据是排好序的，那么我们可以利用它大概的变化率来确定 mid 的值，在一定的情况下能比直接进行二分相率更高。

二分查找我们通过以下策略获取 mid 值：

在插值查找中，我们把策略改成：

（对于这个公式的理解可以参考我们初中学过的相似三角形）

算法代码如下（递归）：

int insertValueSearch(std::vector<int> &nums, int left, int right, int target)
{
    if (left > right || target < nums[left] || target > nums[right])
        return -1;

    //与二分算法的不同主要体现在这里
    int mid = left + (target - nums[left]) / (nums[right] - nums[left]) * (right - left);

    if (nums[mid] == target)
        return mid;
    else if (nums[mid] < target)
        return insertValueSearch(nums, mid + 1, right, target);
    else
        return insertValueSearch(nums, left, mid - 1, target);
}

//重载方法，便于调用
int insertValueSearch(std::vector<int> &nums, int target)
{
    return nums.size() == 0 ? -1 : insertValueSearch(nums, 0, nums.size() - 1, target);
}

插值查找注意事项：

• 对于数据量较大，关键字分布比较均匀的查找来说插值插值速度较快
• 关键字分布不均匀的情况下，该方法不一定比二分查找好

---

斐波那契查找算法（黄金分割法）

斐波那契查找原理与前两种相似，仅仅改变了中间节点 mid 的获取策略，mid 不再是中间或插值得到，而是位于黄金分割点附近。

黄金分割点可以通过斐波那契数列获取近似值，即斐波那契的前后两项相除所得结果，越往后越趋近于黄金分割率。对于这个算法这里不多阐述，个人感觉这就是一个玄学算法。

代码如下：

/*
    这段代码是用我以前学算法时写的java代码直接改过来的，
    可能有些地方写的有点奇怪，感兴趣的话上网查一下吧。
*/

#define FIB_SIZE 20

//因为后面mid=low+F(k-1)-1，需要先获取一个斐波那契数列
void setFib(int f[])
{
    f[0] = 1;
    f[1] = 1;
    for (int i = 2; i < FIB_SIZE; i++)
        f[i] = f[i - 1] + f[i - 2];
}

/**
 * 编写斐波那契查找算法
 * 使用非递归的方式编写算法
 *
 * @param a   数组
 * @param key 需要查找的关键码（值）
 * @return 返回对应的下标，如果没有返回-1
 */
int fibSearch(std::vector<int> &a, int key)
{
    int low = 0;
    int high = a.size() - 1;
    int k = 0;   //斐波那契分割数值下标
    int mid = 0; //存放mid值

    int f[FIB_SIZE]; //获取斐波那契数列
    setFib(f);

    //获取到斐波那契分割数值下标
    while (high > f[k] - 1)
        k++;

    //因为f[k]值可能大于数组长度，因此，需要构造一个新的数组
    //不足的部分使用0填充
    int tempLen = f[k];
    int *temp = (int *)calloc(tempLen, sizeof(int));
    for (int i = 0; i < tempLen; i++)
        temp[i] = i < a.size() ? a[i] : 0;

    //需要使用a数组的最后的数填充temp
    for (int i = high + 1; i < tempLen; i++)
        temp[i] = a[high];

    //使用while循环处理，查找数key
    while (low <= high)
    {
        mid = low + f[k - 1] - 1;
        if (key < temp[mid])
        { //说明应该继续向数组的前面查找（左边）
            high = mid - 1;
            //为什么是k--
            //说明：
            //1.全部元素 = 前面的元素 + 后面的元素
            //2.f[k] = f[k-1] + f[k-2]
            //因为前面有f[k-1]个元素，所以可以继续拆分f[k-1] = f[k-2] + f[k-3]
            //即在f[k-1]的前面继续查找k--
            //即下次循环mid = f[k-1-1]-1
            k--;
        }
        else if (key > temp[mid])
        { //说明应该向数组的右边查找
            low = mid + 1;
            //为什么是k -= 2
            //说明：
            //1.全部元素 = 前面的元素 + 后面的元素
            //2.f[k] = f[k-1] + f[k-2]
            //3.因为后面有f[k-2]个元素，所以可以继续拆分f[k-1] = f[k-3] + f[k-4]
            //4.即在f[k-2]的前面进行查找k -= 2
            //5.即下次循环mid = f[k-1-2]
            k -= 2;
        }
        else
        { //找到
            free(temp);
            //需要确定返回的是那个下标
            if (mid <= high)
                return mid;
            else
                return high;
        }
    }
    free(temp);
    return -1;
}

三分算法

在前面的算法都要求所查找的数组或者函数都必须是单调增或者单调减的，当数组或者函数不是单调时（如二次函数），二分算法就无能为力了，因为在这种情况下，无法确定要找的点到底是在 mid 的左边还是右边，为了解决这种问题，这里介绍另外一种算法 —— 三分算法。

三分算法是用于寻找凹/凸函数（如二次函数）在某个区间的最值的算法，这种算法的思路跟二分法也很相似，顾名思义三分法就是将一个区间分成三个部分，通过中间的两个点的数值关系来逐步缩小区间，当区间足够小是，区间的边界就可以认为是函数的解。

三分算法的关键就是如何根据两个 mid 来确定最值的位置，用文字不太容易描述，这里用图片列出了 mid_l（靠左边的中间点）和 mid_r（靠右边的中间点）与最值点位置的几种可能的情况情况：

在最值点左边	在最值点右边	在最值点两边
left = mid_l	right = mid_r	left = mid_l 或 right = mid_r

表格的第三行表示可行的策略，我们需要判断 mid_l 和 mid_r 分别所对应的函数值的关系，根据这个关系来排除掉一部分区间，从而逐步缩小区间。综合三种情况得知我们每次循环只需要排除掉与最值点较远的一个区间就行了（因为无法判断是上面的哪一种情况）。

算法代码如下：

double f(double x)
{
    return x * x; //以y=x^2为例
}

double getMinValue(double left, double right)
{
    double mid_l, mid_r;

    //“1E-8”可理解为x的精度，这个数字越小结果越精确
    while (right - left > 1E-8)
    {
        //此处不一定需要三等分，分得不均匀也可以
        mid_l = left + (right - left) / 3;
        mid_r = left + (right - left) / 3 * 2;

        if (f(mid_l) > f(mid_r))
            left = mid_l;
        else
            right = mid_r;
    }

    return f(left);
}

这段代码可以用于计算凹函数的最小值，同样的，计算凸函数的最大值也是用相同的方法，只需要改一下条件即可。

参考资料

https://leetcode-cn.com/tag/binary-search/

https://leetcode-cn.com/leetbook/detail/binary-search/

https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95

https://www.cnblogs.com/kyoner/p/11080078.html

https://www.cnblogs.com/techflow/p/12131376.html