在 C 中二分法Binary Search是一种用于在有序数组中查找特定元素的高效算法。基本原理二分法的核心思想是利用数组的有序性每次将搜索区间缩小一半。它通过比较目标值与区间中间元素的值来决定下一步的搜索方向直到找到目标值或者确定目标值不存在于数组中。算法步骤初始化设置两个指针left和right分别指向数组的起始位置和结束位置。计算中间位置在每次循环中计算中间位置mid通常使用公式mid left (right - left) / 2。本质上还是lr/2先多减再回加可以避免lr过大的情况这样可以避免left和right相加时可能出现的溢出问题。比较中间元素与目标值如果中间元素arr[mid]等于目标值target则表示找到了目标返回mid。如果arr[mid]大于target说明目标值在左半部分更新right mid - 1继续在左半区间搜索。如果arr[mid]小于target说明目标值在右半部分更新left mid 1继续在右半区间搜索。4.循环执行重复步骤 2 和 3直到left大于right此时表示目标值不在数组中返回 -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; // 找到目标元素返回其索引 } else if (arr[mid] target) { left mid 1; // 目标元素在右半部分 } else { right mid - 1; // 目标元素在左半部分 } } return -1; // 未找到目标元素 }复杂度分析复杂度时间复杂度二分法每次迭代都将搜索区间减半因此时间复杂度为 O(log n)其中 n是数组的元素数量。这使得二分法在处理大规模有序数据时非常高效。O(log n)的由来:这个查找过程会一直持续也就会一直除以2直到我们找到目标元素或者确定目标元素不存在于数组中。当查找范围缩小到只剩下 1 个元素时就不能再继续二分了此时可以认为查找结束。即当时查找过程停止。 n,k所以二分法的时间复杂度就表示为O(log n)。二分基础练习题洛谷P2249C STL 中用于二分查找的核心函数用于在已排序的区间中查找第一个大于目标值的元素。函数作用针对示例{1,2,4,4,5,7}查找4lower_bound找第一个value的元素返回指向第一个4的迭代器下标 2upper_bound找第一个value的元素返回指向5的迭代器下标 4auto it upper_bound(v.begin(), v.end(), x);如果返回值不是end()可以直接用*it获取该元素的值。通过it - v.begin()将迭代器转换为数组下标仅适用于vector、string等随机访问迭代器