写的许多二分查找中基本都是因为一个等号而报错好多次, 下面是我之前总结的:

向上取整: mid = l + (r - l + 1 >> 1)

寻找目标数最后一次出现的位置或最后一个小于它的位置:

if(a[mid] <= x) l = mid;
else r = mid - 1;

寻找第一个比目标数小的数的位置:

if(a[mid] < x) l = mid; //与上面的相比就是少了一个等号
else r = mid - 1;

向下取整: mid = l + r >> 1

寻找目标数第一次出现的位置或第一个大于目标数的数的位置:

if(a[mid] >= x) r = mid;
else l= mid + 1;

寻找第一个比目标数大的数的位置:

if(a[mid] > x) r = mid; //与上面的相比就是少了一个等号
else l= mid + 1;

这里插入两个好用的函数

• lower_bound(a.begin(), a.end(), x):返回容器中第一个值【大于或等于】x的元素的iterator位置
• upper_bound(a.begin(), a.end(), x): 返回容器中第一个值【大于】x的元素的iterator位置

如果val大于数组中全部元素，返回的是last。(注意：数组下标越界)

所以如果查找某个数字时, 两个函数的返回值一样, 那么这个数字就不存在, 所以关于查找一个数出现的位置区间我们可以这样:

输出的结果就是下标区间啦(不存在则是-1);

auto l = lower_bound(a.begin(), a.end(), L);
auto r = upper_bound(a.begin(), a.end(), L);
if(l == r) cout << "-1 -1" << endl;
else cout << l-a.begin() << " " << r - a.begin() - 1 << endl;