...
二分查找最直接的场景是查找给定数值的位置，但是在某些场景下，特别是排序数组中存在重复元素时，二分查找也可以用于查找给定元素出现的左边界或右边界，也就是lower_bound和upper_bound。
二分查找典型实现：
| 代码块 | ||
|---|---|---|
| ||
// 查找数组a中val的出现位置
int binary_search(int a[], int n, int val) {
int ret = -1; // 查找失败返回-1
int left = 0;
int right = n - 1;
int mid;
while(left <= right) {
mid = left + (right - left) >> 1; // 防止直接平均可能的溢出问题
if(a[mid] < val) {
left = mid + 1;
} else if(a[mid] > val) {
right = mid - 1;
} else { // 相等情况放到最后，减少分支预测，因为多数搜索情况不是大于就是小于
ret = mid;
break;
}
}
return ret;
} |
对于左右边界的查询，可借助标准库的lower对于左右边界的查询，可借助标准库的lower_bound()和upper和upper_bound()函数，如下：
| 代码块 | linenumbers | true
|---|
template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val); template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val); template <class ForwardIterator, class T, class Compare> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); |
...