查看源

二分查找，也称折半查找，用于在有序数组中查询特定元素。

二分查找最直接的场景是查找给定数值的位置，但是在某些场景下，特别是排序数组中存在重复元素时，二分查找也可以用于查找给定元素出现的左边界或右边界，也就是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。

此外，标准库中还有一个binary_search(first, last, val)方法，这个方法用于判断区间内是否存在val元素，返回bool值，以下是这个方法的实现：

template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{
  first = std::lower_bound(first,last,val);
  return (first!=last && !(val<*first));
}