二分查找,也称折半查找,用于在有序数组中查询特定元素。
二分查找的情形不止一种,而是有三种,分为以下情况:
- 查找数值,只要找到对应的值即可。
- 查找左侧边界,针对查询元素存在重复的情况,查找左侧出现的第一个位置。
- 查找右侧边界, 同上。
数值查找:
二分查找最直接的场景是查找给定数值的位置,但是在某些场景下,特别是排序数组中存在重复元素时,二分查找也可以用于查找给定元素出现的左边界或右边界,也就是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_bound()和upper_bound()函数,如下:
代码块 | ||
---|---|---|
| ||
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); |
函数说明:
lower_bound(first, last, val)
:查找区间内第一个大于或等于val的元素位置,查找失败返回last。upper_bound(first, last, val)
:查找区间内第一个大于val的元素位置,查找失败返回last。