企业官网建设流程全解析

二分查找 (Binary Search)

像“猜数字”游戏一样，每次直接猜正中间的数。如果猜大了，就把右半边的范围全扔掉；如果猜小了，就把左半边的范围全扔掉。通过不断“折半”缩小查找范围，每次都能排除掉一半的数据，从而极其高效地找到目标元素。

核心代码

#include <stdio.h> // 二分查找函数：在有序数组中查找目标值 int binarySearch(int arr[], int n, int target) { int left = 0; // 左边界指针 int right = n - 1; // 右边界指针 // 当左边界小于等于右边界时，说明查找区间依然有效 while (left <= right) { // 计算中间位置(这种写法可防止 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; // 循环结束仍未找到，返回 -1 } // 打印数组的辅助函数 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { // 注意：二分查找的前提是数组必须有序！ int arr[] = {12, 22, 25, 34, 64}; int n = sizeof(arr) / sizeof(arr[0]); int target = 25; printf("数组内容："); printArray(arr, n); int result = binarySearch(arr, n, target); // 调用二分查找 if (result != -1) { printf("目标值 %d 的下标为：%d\n", target, result); } else { printf("数组中未找到目标值 %d\n", target); } return 0; }

示例演示

{12, 22, 25, 34, 64}，目标值 target = 25

第 1 次查找：在整体范围 {12, 22, 25, 34, 64} 中查找
目标：通过中间元素判断目标在哪半边。
确定边界：left = 0，right = 4。
计算中点：mid = 0 + (4 - 0) / 2 = 2。中间元素 arr[2] = 25。
比较：25 == 25，命中目标！
第 1 次结束：直接找到目标，返回下标 2。
(为了演示折半过程，我们假设目标值 target = 34)
第 1 次查找：在整体范围 {12, 22, 25, 34, 64} 中查找
确定边界：left = 0，right = 4。
计算中点：mid = 2，中间元素 arr[2] = 25。
比较：25 < 34，说明目标在右侧。更新左边界 left = mid + 1 = 3。
当前查找范围缩小为：[34, 64]

第 2 次查找：在剩余范围 {34, 64} 中查找
确定边界：left = 3，right = 4。
计算中点：mid = 3 + (4 - 3) / 2 = 3。中间元素 arr[3] = 34。
比较：34 == 34，命中目标！
第 2 次结束：找到目标，返回下标 3。

复杂度

时间复杂度是\(O(logn)\)(每次查找都能排除一半的数据，查找次数随数据规模呈对数级增长)
空间复杂度是\(O(1)\)(迭代法仅需常数级的额外空间用于维护左右边界和中点指针)