折半查找

说明

使用二分的思想进行查找

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;
}
//金海峰
LL binary_search(LL start, LL end, LL a)
{
    LL l = start;
    LL r = end;
    while (l < r)
    {
        LL mid = (l + r) / 2;
        if (ok(mid, a))
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

results matching ""

    No results matching ""