JavaScript二分查找算法详解

大家好，今天本人给大家带来文章《JavaScript二分查找实现方法》，文中内容主要涉及到，如果你对文章方面的知识点感兴趣，那就请各位朋友继续看下去吧~希望能真正帮到你们，谢谢！

二分查找适用于已排序数组，时间复杂度O(log n)，通过每次比较中间元素缩小区间；基础迭代实现用left/right指针和mid=left+Math.floor((right−left)/2)避免溢出，未找到返回−1；含重复元素时可找左右边界，需调整收缩逻辑并校验越界；递归版逻辑清晰但推荐迭代版；使用前须确保数组升序、非频繁变动且长度适中。

二分查找适用于已排序的数组，时间复杂度为 O(log n)，比线性查找高效得多。核心思路是每次比较中间元素，根据大小关系排除一半区间，持续缩小区间直到找到目标或确定不存在。

基础实现（非递归）

用左右两个指针控制搜索范围，循环更新中点位置：

• 初始化 left = 0，right = arr.length - 1
• 循环条件为 left <= right（闭区间）
• 计算中点用 mid = left + Math.floor((right - left) / 2)，避免整数溢出
• 若 arr[mid] === target，直接返回 mid
• 若 arr[mid] < target，说明目标在右半部分，更新 left = mid + 1
• 若 arr[mid] > target，说明目标在左半部分，更新 right = mid - 1
• 循环结束未找到，返回 -1

查找边界值（左/右插入位置）

当数组含重复元素时，常需找第一个或最后一个等于 target 的位置，本质是找「左边界」或「右边界」：

• 左边界：缩小右边界时用 right = mid - 1，相等时不立即返回，继续向左搜
• 右边界：缩小左边界时用 left = mid + 1，相等时继续向右搜
• 最终返回 left（左边界）或 right（右边界），注意校验是否越界或匹配

递归写法（理解逻辑用）

递归版本更直观体现“分而治之”，但实际项目中推荐迭代版（无调用栈开销、不易栈溢出）：

• 函数接收 arr, target, left, right 四个参数
• 递归终止条件：left > right → 返回 -1
• 中间逻辑同迭代版，只是用 return search(arr, target, newLeft, newRight) 替代循环更新

使用注意事项

二分查找不是万能的，用前务必确认：

• 数组必须升序排列（降序需调整比较逻辑）
• 若数组动态变化频繁，维护有序性成本可能高于查找收益
• 小数组（如长度 < 50）用线性查找反而更快（省去计算和分支判断）
• JS 中 Array.prototype.indexOf() 不是二分，它总是线性遍历

基本上就这些。写对边界和中点公式，再结合具体需求选模板，就能稳稳拿下有序数组查找问题。

以上就是《JavaScript二分查找算法详解》的详细内容，更多关于二分查找的资料请关注golang学习网公众号！