二分查找
入门经典的对半缩减策略，是有序数组查找的基础模板。
// 搜索输入
定义数组和目标值
可视化演示开发中
二分查找 的交互式动画即将上线，敬请期待。
1int binarySearch(int arr[], int n, int target) {
2 int left = 0, right = n - 1;
3 while (left <= right) {
4 int mid = left + (right - left) / 2;
5 if (arr[mid] == target) return mid;
6 if (arr[mid] < target) {
7 left = mid + 1;
8 } else {
9 right = mid - 1;
10 }
11 }
12 return -1;
13}
复杂度分析
时间 O(log n)
空间 O(1)
最优 O(1)
最坏 O(log n)
算法讲解
二分查找要求数组已经按升序排列，否则"比中点大还是小"这个判断就无法正确缩小区间。
每一轮都会同时标出 left、right 和 mid，你可以把它看成"候选范围不断对半折叠"的过程。
若中点值小于目标值，就说明左半边不可能再命中；若中点值大于目标值，则右半边可以整体排除。
相比线性查找逐个扫，二分查找的核心优势在于每次比较都能丢掉一半候选区间。
它非常适合静态有序数组、词典索引、配置表查询等"可排序且可随机访问"的场景。
时间复杂度为 O(log n)，空间复杂度为 O(1)。