二分查找

输入

• 一个有序的容器
• 待查找元素

输出

元素在容器中的位置

时间复杂度

O(logn)

空间复杂度

O(1)

例子

容器：1 3 5 8 9 10 15 27
元素：9
返回值：4

find

为了简单起见，元素类型限定为int，容器为vector。后面可以定义成模板函数，支持任意元素类型和任意支持前向迭代器的容器。

// 二分搜索，从容器a中查找元素val
// 返回元素出现的位置。如果不存在，返回-1
int binarySearch(const vector<int> &a, int val) {
    int begin = 0, end = a.size() - 1, mid;
    while (begin <= end) {
        mid = (begin + end) / 2;
        if (a[mid] < val)
            begin = mid + 1;
        else if (a[mid] > val)
            end = mid - 1;
        else
            return mid;
    }
    return -1;
}

变型

之前的二分查找是查找元素的位置，要求精确匹配元素的值：如果存在就返回位置，如果不存在就返回-1. 其实有时候我们不需要进行精确匹配。例如对于容器：1 3 5 8 9 10 15 27，我们要查找7，显然7在容器里不存在，但是我们还是希望算法能够返回一个大概的位置。这个位置可能有两个：5或者8。5是7的下界(lower bound)，8是7的上界(upper bound)。

还有一种情况，假设容器允许出现重复元素，例如1 3 5 5 5 8 9 10 15 27。这时5的下界就是下标为2的5，5的下界就是下标为4的5。

lower bound

// 二分下界搜索，在容器a中查找元素val的下界
// 如果下界不存在，返回-1
int binarySearchLowerBound(const vector<int> &a, int val) {
    if (val < a.front()) return -1;
    int begin = 0, end = a.size() - 1, mid;
    while (begin < end) {
        mid = (begin + end) / 2;
        if (a[mid] < val)
            begin = mid + 1;
        else
            end = mid;
    }
    return a[begin] == val ? begin : begin - 1;
}

upper bound

// 二分上界搜索，在容器a中查找元素val的上界
// 如果上界不存在，返回-1
int binarySearchUpperBound(const vector<int> &a, int val) {
    if (val > a.back()) return -1;
    int begin = 0, end = a.size() - 1, mid;
    while (begin < end) {
        mid = (begin + end) / 2 + 1;
        if (a[mid] > val)
            end = mid - 1;
        else
            begin = mid;
    }
    return a[begin] == val ? begin : begin + 1;
}