算法-二分查找

二分查找 (Binary Search)像“猜数字”游戏一样每次直接猜正中间的数。如果猜大了就把右半边的范围全扔掉如果猜小了就把左半边的范围全扔掉。通过不断“折半”缩小查找范围每次都能排除掉一半的数据从而极其高效地找到目标元素。核心代码#include stdio.h // 二分查找函数在有序数组中查找目标值 int binarySearch(int arr[], int n, int target) { int left 0; // 左边界指针 int right n - 1; // 右边界指针 // 当左边界小于等于右边界时说明查找区间依然有效 while (left right) { // 计算中间位置(这种写法可防止 leftright 过大导致整型溢出) 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 0right 4。计算中点mid 0 (4 - 0) / 2 2。中间元素 arr[2] 25。比较25 25命中目标第 1 次结束直接找到目标返回下标 2。(为了演示折半过程我们假设目标值 target 34)第 1 次查找在整体范围 {12, 22, 25, 34, 64} 中查找确定边界left 0right 4。计算中点mid 2中间元素 arr[2] 25。比较25 34说明目标在右侧。更新左边界 left mid 1 3。当前查找范围缩小为[34, 64]第 2 次查找在剩余范围 {34, 64} 中查找确定边界left 3right 4。计算中点mid 3 (4 - 3) / 2 3。中间元素 arr[3] 34。比较34 34命中目标第 2 次结束找到目标返回下标 3。复杂度时间复杂度是\(O(logn)\)(每次查找都能排除一半的数据查找次数随数据规模呈对数级增长)空间复杂度是\(O(1)\)(迭代法仅需常数级的额外空间用于维护左右边界和中点指针)