输入
- 一个有序的容器
- 待查找元素
输出
元素在容器中的位置
时间复杂度
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;
}
