本文详解 JavaScript 中二分查找的三种核心场景：查找特定数值、寻找左侧边界及右侧边界。通过对比不同搜索区间（左闭右开与左闭右闭）的实现方式，深入分析 mid 计算防溢出技巧及边界收缩逻辑，帮助开发者在算法面试中准确手写二分查找代码。
你是否遇到过这样的刷题经历：起初面对题目毫无头绪，匆忙查阅题解后恍然大悟，随即按思路开始作答。然而中途卡壳，再次回顾题解，最终勉强完成。回头看实现代码，一步步拆解发现其实并不复杂。
然而某天面试时，考官恰好问及你曾做过的题目，此时你仅模糊记得做过，具体思路却已遗忘殆尽。
我也常陷于此种困境，自认算法基础薄弱，因此决定以文章形式记录学习算法的历程，作为一种输出。有人言“学习算法如同解数学题，记住公式，识别题型后套用即可”，那便以此法尝试。
二分查找是算法学习中的关键部分，且在面试中常要求手写实现。
本文探讨三个最常用的二分查找场景：查找一个特定数值、查找左侧边界、查找右侧边界。
二分查找公式
function binarySearch(nums, target) {
let left = 0
let right = ...
while(...) {
const mid = Math.floor(left + (right - left) / 2)
if(nums[mid] === target) {
...
} else if(nums[mid] < target) {
left = ...
} else if(nums[mid] > target) {
right = ...
}
}
return ...
}分析二分查找技巧时，不应出现 else，而应将所有情况用 else if 清晰表述，以展示所有细节。
Math.floor(left + (right - left) / 2) 其实与 Math.floor((left +right)/2) 的结果一致。但当 left 和 right 数值较大时，直接相加可能导致溢出。使用 Math.floor(left + (right - left) / 2) 可有效防止此类溢出问题。
寻找一个数
var search = function (nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return -1;
};力扣第 704 题二分查找，这是二分查找最简单的题型，绝大多数二分查找题型均基于此拓展。
首先需确定搜索区间。因定义的 right 为 nums.length - 1，故搜索区间为 [left, right]，两端均闭合。当找到目标元素时，停止搜索并退出循环，返回目标值对应的索引。
若未找到目标元素，当循环终止条件 left === right + 1 满足时，直接返回 -1 即可。
缺陷
若给定有序数组 nums = [1,2,2,2,3]，target 为 2，上述方法返回的索引是 2。若想获取 target 在 nums 中最左边或最右边满足条件的值，此方法便存在局限。
有人或许想到找到 target 的值后，向左或向右进行线性搜索。但这将难以保证二分查找对数级的时间复杂度。
寻找最左边满足条件的值
方式一
function leftBound(nums, target) {
let left = 0;
let right = nums.length;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
if (left === num.length) return -1;
return nums[left] === target ? left : -1;
}上述是一种常见代码形式，但与初始框架匹配。此处 while 中使用 < 而非 <=，因定义 right 时为 nums.length 而非 nums.length-1，说明搜索区间为 [left,right)，左闭右开。故终止条件为 left == right 时。
另有一个不同点，使用 right = mid 而非 right = mid - 1，这受搜索区间影响。因搜索区间为 [left,right) 左闭右开，当 nums[mid] 被检测到时，下一步应缩小搜索区间。若 nums[mid] === target，虽已找到 target 的值，但不立即返回，而是将搜索区间缩小为 [left, mid)。随后不断向左收缩，直至锁定左侧边界，即当 left == right 时。
最后考虑越界情况，若 left 的值为 nums.length，说明查找左侧边界已超出搜索区间，即 target 的值比所有数都大。若 left 的值为 target，说明找到后直接返回。此时返回 left 与返回 right 等效，因终止条件为 left == right。
方式二
function leftBound(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] === target) {
right = mid - 1;
}
}
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}方式一的搜索区间为 [left, right)。方式二将搜索区间改为 [left, right] 左闭右闭。因 right 取值为 nums.length - 1，即 nums 的最后一个值。while 的终止条件为 left == right + 1，即代码中使用的 <=。
此时使用 right = mid - 1 而非 right = mid，因搜索区间改变，[left,right] 两端均闭合。
最后判断边界条件，若 left >= nums.length 说明已超出搜索区间，或 left 的值与 target 不同则说明未找到。
如此便与第一种二分搜索算法统一，均为两端闭合的搜索区间，且最后返回 left 变量的值。不过我个人更倾向于这种方式。
寻找最右侧满足条件的值
方式一
function rightBound(nums, target) {
let left = 0;
let right = nums.length;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
if (left === 0) return -1;
return nums[left + 1] === target ? left - 1 : -1;
}此方式与寻找左侧边界类似，仍使用搜索区间为 [left, right) 左闭右开的方式。关键点在于当 nums[mid]=== target 时，设置 left=mid+1。这样可将搜索区间变为 [mid+1, right)。利用此方式不断增大左边界 left 的值，使区间不断向右靠拢，最终到达右边界。
但此方式最后返回的是 left - 1。因 while 的终止条件为 left === right，此时循环已退出。若已找到，left 则比要锁定的目标索引多 1。因为下面这段代码
if(nums[mid] === target) {
left = mid + 1
}所以最后的目标值需 left - 1。
方式二
function rightBound(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (nums[mid] === target) {
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
if (right < 0 || nums[right] !== target) {
return -1;
}
return right;
}此处与左侧边界类似，搜索区间为 [left, right] 左闭右闭。
二分查找大致即这三种情况，也可理解为一种情况不断延伸。记住套路后，便开始刷题巩固吧！
以上就是 JavaScript 中二分查找的例题详解的详细内容，更多关于 JavaScript 二分查找的资料请关注本站其它相关文章！