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

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define ULL unsigned long long
#define all(v) v.begin(), v.end()
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
constexpr int N =  1 * 1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

vector<int> vec;
int find1(int n)
{
    return lower_bound(all(vec),n) - vec.begin();
}
int find2(int n)
{
    return upper_bound(all(vec),n) - vec.begin();
}
void solve()
{
    int n,q;
    cin >> n >> q;
    vec.resize(n);
    for(int i=0;i<n;i++) cin >> vec[i];
    while(q--)
    {
        int x;
        cin >> x;
        int l = find1(x) , r = find2(x)-1;
        if(vec[l] == x && vec[r]==x) cout << l << ' ' << r << '\n';
        else cout << "No answer" << '\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.11.21 23:19:38
 */

不如yxy

#include <bits/stdc++.h>
#define int long long
#define pow_of_two(n) (n & -n == n) 
using namespace std;
#define lowbit(x) (x) & (-x)
// const int N = 1e6 + 10;
int n , q , ans;
vector<int> a;

int search2(int x)
{
    int l = 0 , r = n - 1 ;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (a[mid] <= x) l = mid;
        else r = mid - 1;

    }

    return l;
}


int search1(int x)
{
    int l = 0 , r = n - 1 ;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;

    }

    return l;
}

inline void solve() 
{   
    cin >> n >> q;
    for (int i = 1 , temp ; i <= n ; i ++ ) cin >> temp , a.push_back(temp);

    while (q -- ) 
    {
        int x;
        cin >> x;
        int ans = search1(x);
        if (a[ans]!= x) cout << "No answer" << endl;
        else
        {
            cout << ans << " ";
            ans = search2(x);
            cout << ans << endl;
        }   
    }    

    return ;
}


signed main()
{
    ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
    solve();
    return 0;
}