[toc]

二分查找

二分查找中常见的疑惑

二分写法通常有很多种，有的时候自己在写的时候往往会纠结与上下界、开闭区间、边界条件等等情况，接下来就对二分写法做一个整理，主要思路来源于知乎。

C++<Alogorithm>标准写法

//返回[first, last)中第一个不小于value的值的位置。
int lower_bound(int *array, int first, int last, int value)
{
    while(first < last)
    {
        int mid = first + (last - first) / 2;
        if(array[mid] < value)
            first = mid + 1;
        else last = mid;
    }
    //return last也可以，区间为空时first、last重合。
    return first;
}

Notes

• 区间一定是左闭右开，这样做的好处有很多。
  • 区间两端的数值之间相减正好为区间的长度。[a,b)的长度length = b-a。
  • 相邻区间判断比较简单，[0,2)和[2,4)可以很轻易地看出。
• 如果想求的不是 第一个不小于value的值，而是 任意等于value的值，只需要在循环开始加一个判断array[mid] == value。

严格定义二分查找定义

定义lower_bound函数：给定数组array、区间[first, last)和一个目标值value，返回区间第一个大于等于value的元素的位置。若不存在，返回last。

如何取中点

算法中取中点是这样写的：

int mid = first + (last - first) / 2; //防溢出

• 上位中位数：first + length / 2;
• 下位中位数：first + (lenth - 1) / 2;
• 以上两个均可以使用。

边界条件

参考：https://www.zhihu.com/question/36132386