二分查找适用于已排序数组，时间复杂度O(log n)，通过比较中点元素不断缩小区间；基础迭代实现用左右指针和Math.floor计算中点，递归版需注意栈溢出，插入位置变体返回左边界收敛点。
二分查找适用于已排序的数组，时间复杂度是 O(log n)，比线性遍历快得多。核心思路是每次比较中间元素，根据大小关系排除一半区间，不断缩小区间直到找到目标或确定不存在。
基础实现（非递归）
用左右两个指针控制搜索范围，循环更新中点位置：
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
<p>while (left <= right) {
const mid = Math.floor((left + right) / 2);</p><pre class="brush:php;toolbar:false;">if (arr[mid] === target) {
return mid; // 找到，返回索引
} else if (arr[mid] < target) {
left = mid + 1; // 目标在右半边
} else {
right = mid - 1; // 目标在左半边
}}
return -1; // 未找到 }
- 注意使用 Math.floor 防止 mid 偏移（尤其数组长度为偶数时）
- 循环条件是 left ，不是
left ，否则可能漏掉最后一个元素 - 数组必须升序排列；若降序，只需调换
left和right的更新逻辑
递归写法（理解原理更直观）
把“缩小范围”转化为函数自身调用，逻辑更贴近二分思想：
立即学习“Java免费学习笔记（深入）”；
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
if (left > right) return -1;
<p>const mid = Math.floor((left + right) / 2);</p><p>if (arr[mid] === target) return mid;
if (arr[mid] < target) {
return binarySearchRecursive(arr, target, mid + 1, right);
} else {
return binarySearchRecursive(arr, target, left, mid - 1);
}
}- 递归版本默认参数让调用更简洁：
binarySearchRecursive([1,3,5,7], 5) - 注意防止栈溢出——实际项目中大数组建议用迭代版
找插入位置（扩展用法）
如果目标不存在，想返回它“应该插入的位置”（保持有序），只需稍改返回值：
function searchInsertPosition(arr, target) {
let left = 0;
let right = arr.length;
<p>while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left; // 插入点索引
}- 这里
right初始设为arr.length，循环条件用left - 当
arr[mid] >= target时，right = mid，确保左边界收敛到插入点 - 这个变体常用于实现类似
Array.prototype.findIndex或构建有序集合
注意事项和常见坑
- 数组必须有序：二分查找不检查是否有序，输错数据会导致结果错误或死循环
-
整数溢出风险（极少见）：
left + right在超大数组中可能超过Number.MAX_SAFE_INTEGER，可改用left + Math.floor((right - left) / 2) - 重复元素处理：标准二分只保证找到其中一个；如需最左/最右位置，需额外调整边界收缩逻辑
- JavaScript 数组方法如
indexOf不是二分，它是线性查找，别误用
