在计算机科学中，二分查找算法也称折半搜索算法，对数搜索算法，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。二分查找算法在最坏情况下是对数时间复杂度的，需要进行 $O(logn)$ 次比较操作。-- 维基百科。

代码实现上述思路很简单

int l = 0, r = n - 1;//给定区间 [l, r]
while (l < r)//区间还未缩成一个点
{
    int mid = (l + r) >> 1;//折半搜索
    if (a[mid] >= k) r = mid;//如果 a[mid]>= 目标元素，那么此时答案一定在[l, mid]
    else l = mid + 1;//否则的话答案一定在[mid + 1, r]

  //[l, mid]，和 [mid + 1, r] 的意思为新区间 [l, r]
}

但是该算法在 l = mid 时 (有坑)，写的时候很容易出现死循环，二分是个简单的算法但是 $90\%$ 的程序员无法正确无误的写出。

下面举个例子是怎么陷入死循环的，给定数组 $[1, 3, 3, 3, 5]$，方便理解我们认为下标是从 $1$ 开始的 （从零开始是一样的都会有边界问题），我们现在要求目标值 $3$ 最后一个出现的位置。

我们令 int mid = (l + r) >> 1; 那么 $mid = 3$, 由于 $a[3] \leq 3$ ,所以 $l = mid$，此时区间为 $[3, 5]$。

我们继续二分令 int mid = (l + r) >> 1; $a[4]$ 仍是 $\leq 3$，所以 $l = mid$，此时区间为 $[4, 5]$，算法继续。

令 int mid = (l + r) >> 1; $a[4]$ 仍是 $\leq 3$，所以 $l = mid$，此时区间仍为 $[4, 5]$，因为 (4 + 5) >> 1 == 4，$l$ 永远等于 $4$ 此时陷入死循环。

令 int mid = (l + r + 1) >> 1;即可避免上述问题。加强记忆 $l = mid$ 时要加 $1$

小技巧：整数上取整，$ceil(n / m) == (n + m - 1) / m .$

下标从 $0$ 代码实现

#include<iostream>
//背下我的代码，不要做任何改动
using namespace std;

const int N = 200010;
int a[N];
int n, q;

int main()
{
    cin >> n >> q;

    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

    while (q--)
    {
        int k;
        cin >> k;
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (a[mid] >= k) r = mid;//左边第一个出现的位置
            else l = mid + 1;
        }
        if (a[l] != k) cout << "No answer" << endl;
        else
        {
            cout << l << ' ';
            int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = (l + r + 1) >> 1;
                if (a[mid] <= k) l = mid;//右边第一个出现的位置
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }

    return 0;
}

下标从 $1$ 代码实现

#include<iostream>

using namespace std;

const int N = 200010;
int a[N];
int n, q;

int main()
{
    cin >> n >> q;

    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    while (q--)
    {
        int k;
        cin >> k;
        int l = 1, r = n;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (a[mid] >= k) r = mid;
            else l = mid + 1;
        }
        if (a[l] != k) cout << "No answer" << endl;
        else
        {
            cout << l - 1 << ' ';
            int l = 1, r = n;
            while (l < r)
            {
                int mid = (l + r + 1) >> 1;
                if (a[mid] <= k) l = mid;
                else r = mid - 1;
            }
            cout << l - 1 << endl;
        }
    }

    return 0;
}