折半查找

说明: 使用二分的思想进行查找 array为被查找数组 l为区间左端点 r为区间右端点 v为目标值 查询时间复杂度$O(\log n)$ 使用方法:

• 按值查找:调用binary_search(array, l, r, v),在闭区间[l, r]内查找目标值v,命中返回下标,否则返回-1。
• 二分答案(方法1/方法2):自己实现判定函数judge(mid)(返回mid是否满足条件),然后直接套用下方方法1或方法2的while循环(循环内内联调用judge(mid)),而不是调用binary_search。方法1求满足条件的最大可行值,方法2求满足条件的最小可行值。

Tips: 此模版是求[l, r]闭区间的，而不是求[l, r)开区间的

推荐使用lower_bound()和upper_bound()

int binary_search(int array[], int l,int r, int v)
{
    int left, right, middle;
    left = l, right = r;
    while (left <= right)                      //此处应注意
    {
        middle = (left + right) / 2;
        if (array[middle] > v)
            right = middle - 1;
        else if (array[middle] < v)
            left = middle + 1;
        else
            return middle;                      //此处应注意
    }
    return -1;
}
//方法1:
int ans = 0;
while (l <= r)
{
    int mid = (l + r) >> 1;
    if (judge(mid))
    {
        ans = mid;
        l = mid + 1;
    }
    else
        r = mid - 1;
}
printf("%d\n", ans);
//方法2:
long long l = 0, r = 1e18;
while (l < r)
{
    long long mid = (l + r) >> 1;
    if (judge(mid))
        r = mid;
    else
        l = mid + 1;
}
printf("%d\n", l);