什么是二分查找

二分查找也叫折半搜索，是用来在一个有序数组中查找某一元素的算法。相较于线性查找,二分查找利用了数组的有序性质,通过调整边界快速缩减查找范围,大大提高了查找效率。
线性查找时间复杂度:

• 时间复杂度(最好) O(1)
• 时间复杂度(最坏) O(n)

二分查找时间复杂度:

• 时间复杂度(最好) O(1)
• 时间复杂度(最坏) O(logn)

1. 整数二分的代码实现

以升序数组为例

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (target > arr[mid]) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

STL库里的二分

C++ STL库里有两个查找函数

• std::lower_bound实现了查找首个不小于给定值的元素
• std::upper_bound实现了查找首个大于给定值的元素

二者均采用二分查找，所以使用前应确保数组有序。

传入参数

first, last -要搜索部分范围的迭代器
value -要与元素比较的值

返回值

指向范围首个符合条件的元素的迭代器，在找不到这种元素时返回last

要得到符合条件的元素的下标只需要使用返回迭代器减去first即可

比如

---
int a[5] = {1,3,5,7,9};
int loc = lower_bound(a, a+5, 3) - a; // loc = 1
int loc = upper_bound(a, a+5, 3) - a; // loc = 2
---