二分查找 (Binary Search)
在有序数组中高效查找特定元素的算法
算法原理
二分查找（又称折半查找）要求数组必须是
有序
的。每次将查找范围缩小一半，因此效率极高。
核心步骤：
令 L 为起始下标，R 为结束下标。
计算中间位置 mid = (L + R) / 2。
如果 arr[mid] == target，查找成功！
如果 arr[mid] > target，说明目标在左半边，则 R = mid - 1。
如果 arr[mid] < target，说明目标在右半边，则 L=mid + 1。
重复直到 L > R，查找失败。
演示
生成有序数组
查找目标:
开始查找
停止
L:
-
R:
-
mid:
-
点击"开始查找"以观察
int L = 0, R = n - 1;
while (L <= R) {
int mid = L + (R - L) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) R = mid - 1;
else L = mid + 1;
}
return -1; // 没找到
算法分析
特性
描述
时间复杂度
$$ O(\log n) $$ - 每次砍掉一半，100万个数据也只需找20次！
前提条件
数组必须有序 (Monotonic)