算法中的二分法（二分查找）详解及示例-开发者社区

一、什么是算法中的二分法？

二分法（Binary Search），又称折半查找，是一种在有序数组中查找某个目标值的高效查找算法。其核心思想是：每次将查找范围分成两半，排除不可能包含目标值的一半，仅在可能包含目标值的另一半继续查找，重复此过程，直到找到目标值或确定目标值不存在。

1. 二分查找的必备条件

数组必须是有序的（升序或降序均可，常用升序）；

数组支持随机访问（如数组、vector等数据结构，链表不适用，因为无法快速定位中间元素）。

2. 二分查找的优势（效率对比）

与普通遍历查找（线性查找）相比，二分查找的效率优势极其明显：

线性查找：最坏情况下需要查找n 次（n 为数组长度）；

二分查找：最坏情况下仅需要查找log₂(n)次。

示例：当数组长度n = 1000000（100万）时，线性查找最多需要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，下标是 5

4. 代码说明

该代码实现了最基础的二分查找逻辑，严格遵循“折半-比较-缩范围”的核心，适合查找数组中是否存在某个目标值，并返回其具体位置。

三、示例2：二分查找变种（查找第一个 ≥ 目标值的位置）

实际编程中，除了查找“等于”目标值的位置，更常用的是二分查找的变种，例如查找“第一个大于等于目标值的位置”（即 lower_bound），适用于插入排序、区间查找等场景。

1. 题目描述

给定升序数组[2, 4, 6, 8, 10, 12]，查找第一个大于等于 7 的元素，返回其下标。（预期答案：下标 3，对应元素 8）

2. 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;
}