[数据结构与算法]【更优模板】二分查找总写错？快进来学习！

本文借鉴视频：BiliBili - 二分查找为什么总是写错？

看完视频之后，我直呼牛逼呀！我在这里记录一下。

更优模板，优在哪里？

1.边界清晰，便于确定返回值和循环条件。

2.不会出现left指针和right指针重合的情况，不知道该返回l还是r。（这是非常困扰编程选手的一个地方）

3.l和r最终会逼近target所在的位置，即使target不存在。

一般步骤

1.确定数组已经排序（升序），确定“蓝红”边界。

2.确定我们要返回的值是 l 还是 r ，这个步骤推荐在纸上完成。（用示例完成一次演算）

3.按照代码模板编写代码，这里展示C艹的模板。

示例：Leetcode 35. 搜索插入位置

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    static int searchInsert(vector<int> &nums, int target)
    {
        int l = -1, r = nums.size(), mid;
        while (l + 1 != r)
        {
            mid = (l + r) / 2;
            if (nums[mid] <= target)
                l = mid;
            else
                r = mid;
        }
        return r;
    }
};

int main()
{
    vector<int> nums = {1, 3, 5, 6};
    int target = 7;
    cout << Solution::searchInsert(nums, target);
    return 0;
}