#### 什么是二分查找 二分查找也叫折半搜索，是用来在一个有序数组中查找某一元素的算法。相较于线性查找,二分查找利用了数组的有序性质,通过调整边界快速缩减查找范围,大大提高了查找效率。 线性查找时间复杂度: - 时间复杂度(最好) 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 --- Loading... #### 什么是二分查找 二分查找也叫折半搜索，是用来在一个有序数组中查找某一元素的算法。相较于线性查找,二分查找利用了数组的有序性质,通过调整边界快速缩减查找范围,大大提高了查找效率。 线性查找时间复杂度: - 时间复杂度(最好) 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 --- 最后修改：2024 年 01 月 05 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用，请随意赞赏
