算法中的二分法（二分查找）详解及示例

一、什么是算法中的二分法二分法Binary Search又称折半查找是一种在有序数组中查找某个目标值的高效查找算法。其核心思想是每次将查找范围分成两半排除不可能包含目标值的一半仅在可能包含目标值的另一半继续查找重复此过程直到找到目标值或确定目标值不存在。1. 二分查找的必备条件数组必须是有序的升序或降序均可常用升序数组支持随机访问如数组、vector等数据结构链表不适用因为无法快速定位中间元素。2. 二分查找的优势效率对比与普通遍历查找线性查找相比二分查找的效率优势极其明显线性查找最坏情况下需要查找n 次n 为数组长度二分查找最坏情况下仅需要查找log₂(n)次。示例当数组长度n 1000000100万时线性查找最多需要100万次而二分查找最多仅需约20次效率差距极大。3. 二分查找的基本步骤升序数组通用模板定义查找范围的左边界left 0数组起始下标定义查找范围的右边界right 数组长度 - 1数组末尾下标设置循环条件left ≤ right当左边界不大于右边界时说明还有查找范围计算查找范围的中点mid (left right) / 2通过中点分割范围比较中点元素 arr[mid]与目标值 target若arr[mid] target找到目标值返回当前中点下标若arr[mid] target目标值在中点右侧更新左边界 left mid 1若arr[mid] target目标值在中点左侧更新右边界 right mid - 1。循环结束后若未找到目标值返回 -1表示目标值不存在于数组中。二、示例1基础二分查找查找目标值的下标1. 题目描述给定升序数组[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]查找目标值 11找到则返回其下标找不到则返回 -1。2. C语言代码可直接运行c#include stdio.h// 二分查找函数arr目标数组len数组长度target要查找的目标值int binarySearch(int arr[], int len, int target) {int left 0;// 左边界int right len - 1;// 右边界// 循环查找直到左边界超过右边界while (left right) {int mid (left right) / 2;// 计算中点下标if (arr[mid] target) {return mid;// 找到目标值返回下标}else if (arr[mid] target) {left mid 1;// 目标在右侧更新左边界}else {right mid - 1;// 目标在左侧更新右边界}}return -1;// 循环结束未找到返回-1}int main() {int arr[] {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};// 有序数组int len sizeof(arr) / sizeof(arr[0]);// 计算数组长度int target 11;// 目标值int res binarySearch(arr, len, target);// 调用二分查找函数// 输出结果if (res ! -1) {printf(找到数字 %d下标是 %d\n, target, res);} else {printf(未找到目标值 %d\n, target);}return 0;}3. 运行结果找到数字 11下标是 54. 代码说明该代码实现了最基础的二分查找逻辑严格遵循“折半-比较-缩范围”的核心适合查找数组中是否存在某个目标值并返回其具体位置。三、示例2二分查找变种查找第一个 ≥ 目标值的位置实际编程中除了查找“等于”目标值的位置更常用的是二分查找的变种例如查找“第一个大于等于目标值的位置”即 lower_bound适用于插入排序、区间查找等场景。1. 题目描述给定升序数组[2, 4, 6, 8, 10, 12]查找第一个大于等于 7 的元素返回其下标。预期答案下标 3对应元素 82. C语言代码可直接运行c#include stdio.h// 查找第一个大于等于target的位置arr目标数组len数组长度target目标值int lowerBound(int arr[], int len, int target) {int left 0;// 左边界int right len - 1;// 右边界int ans len;// 初始化为数组长度越界表示未找到符合条件的元素while (left right) {int mid (left right) / 2;// 计算中点下标if (arr[mid] target) {ans mid;// 记录当前符合条件的位置可能是第一个right mid - 1;// 继续往左查找寻找更早更小下标的符合条件的位置} else {left mid 1;// 当前元素小于目标值去右侧查找}}return ans;// 返回第一个≥target的位置若返回len则表示所有元素都小于target}int main() {int arr[] {2, 4, 6, 8, 10, 12};// 有序数组int len sizeof(arr) / sizeof(arr[0]);// 计算数组长度int target 7;// 目标值int pos lowerBound(arr, len, target);// 调用查找函数// 输出结果printf(第一个大于等于 %d 的位置下标是%d\n, target, pos);return 0;}3. 运行结果第一个大于等于 7 的位置下标是34. 代码说明该变种的核心的是“记录符合条件的位置并继续向左缩小范围”确保找到的是“第一个”符合条件的元素。若数组中所有元素都小于目标值最终返回数组长度越界可用于判断插入位置。四、核心总结二分查找的核心有序数组 每次折半缩小范围时间复杂度O(log n)高效的关键n 为数组长度两种常用模板基础模板查找“等于”目标值的下标找不到返回 -1变种模板lower_bound查找“第一个 ≥ 目标值”的下标适用于插入、区间查询等场景。