当前位置：首页 > news >正文

二分查找模板（binary_search）

news 2026/6/1 9:14:13

大家好啊！二分查找是一个很常见的问题，也许大家认为很简单，但是二分查找毕竟可以分为对于递增（不递减）数组，递减（不递增）数组查找不大于，小于，不小于，大于共八种情况，而我们接触到的库函数upper_bound和lower_bound也仅仅只包含两种情况罢了。

如果你常常像我一样为二分查找的条件以及返回值而头昏眼花的话，那么就请看看这篇帖子吧，如果有错误的话欢迎指正~~~

一、何为二分查找？

二、表示二分查找的三种区间选择

三、二分查找

模板：

口诀：

详细代码：

（1）递增（非递减，从小到大）数组

（2）递减（非递增，从大到小）数组

四、结语

一、何为二分查找？

二分查找一般指的是在一个有序数组中，通过不断将搜索范围缩小一半来高效定位某个特定目标值的方法。

核心思想：分治（Divide and Conquer）；

时间复杂度：O(nlog n)；

空间复杂度：O(1)。

二、表示二分查找的三种区间选择

对于二分查找，我们需要取一个左值left和一个右值right，在区间选择上有三种：[left, right],[left, right), (left, right)，这三种取法区别在于：

初始边界设定（left和right的取值）
循环条件（while的判断）
边界更新方式（left和right的调整）

我更习惯使用第一种，也就是闭区间[left, right]，并且返回值为下标，其他两种就不做讲解。

三、二分查找

模板：

int binary_search_template(int arr[], int target) { int lefft = 0, right = arr.size() - 1; while(left <= right) { int mid = left + (right - left) / 2; //防止越界 if (/*情况特定条件*/) ...... else ...... } return /*返回值*/ }

口诀：

情况特定条件：针对于arr[mid]与target的比较，若不大于(<=)，小于(<)，不小于(>=)，大于(>)；

返回值：若为第一个要寻找的值则为left，若为最后一个要寻找的值则为right（需要理解）。

省略号部分：else下面的与返回值统一，若返回值为left，else下则为left = mid + 1，反之。

详细代码：

（1）递增（非递减，从小到大）数组

// 递增数组：找不大于target的最大数 int binary_search_1(int nums[], int target) { int left = 0, right = nums.size()- 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] <= target) left = mid + 1; else right = mid - 1; } //一般情况直接返回(不大于target的最后一个数) return right; } // 递增数组：找小于target的最大数 int binary_search_2(int nums[], int target) { int left = 0, right = nums.size()- 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid + 1; else right = mid - 1; } //一般情况直接返回(小于target的最后一个数) return right; } // 递增数组：找不小于target的最小数 int binary_search_3(int nums[], int target) { int left = 0, right = nums.size()- 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) right = mid - 1; else left = mid + 1; } //一般情况直接返回(不小于target的第一个数) return left; } // 递增数组：找大于target的最小数 int binary_search_4(int nums[], int target) { int left = 0, right = nums.size()- 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] > target) right = mid - 1; else left = mid + 1; } //一般情况直接返回(大于target的第一个数) return left; }

（2）递减（非递增，从大到小）数组

// 递减数组：找不大于target的最大数 int binary_search_5(int nums[], int target) { int left = 0, right = nums.size()- 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] <= target) right = mid - 1; else left = mid + 1; } //一般直接返回（不大于target的第一个数） return left; } // 递减数组：找小于target的最大数 int binary_search_5(int nums[], int target) { int left = 0, right = nums.size()- 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) right = mid - 1; else { left = mid + 1; } //一般直接返回（小于target的第一个数） return left; } // 递减数组：找不小于target的最小数 int binary_search_5(int nums[], int target) { int left = 0, right = nums.size()- 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) left = mid + 1; else right = mid - 1; } //一般直接返回（不小于target的最后一个数） return right; } // 递减数组：找大于target的最小数 int binary_search_5(int nums[], int target) { int left = 0, right = nums.size()- 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] > target) left = mid + 1; else right = mid - 1; } //一般直接返回（大于target的最后一个数） return right; }