折半查找

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

1. 自己定义f()函数
2. binary_search(l, r);其中l, r为对应区间的左右端点值

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:
int l = 0, r = 1e18;
while (l < r)
{
    int mid = (l + r) >> 1;
    if (judge(mid))
        r = mid;
    else
        l = mid + 1;
}
printf("%d\n", l);