二分搜索算法是一种经典算法，它允许我们在时间复杂度为 O(log n) 的有序数组中查找给定元素的索引。在本文中，我们将回顾该算法的工作原理，并学习如何在 Javascript 中实现它。
一个概念性的例子
二分搜索的工作原理是连续将数组一分为二，并查看中间的数字，直到找到匹配项（或未找到匹配项）。假设我们有一个数组 [2, 3, 4, 6, 7, 9, 10]，我们需要找到数字 7 的索引。
在二分搜索中，我们首先确定数组中的中间项，并将其与我们要查找的数字进行比较。我们可以通过将数组开头的索引（0）与数组结尾的索引（6）相加并除以 2 来找到中间索引。换句话说，middle = (start + end) / 2 = (6 + 0) / 2 = 3。
索引 3 处的数字是 6。我们将其与我们要查找的数字 7 进行比较。由于 6 小于 7，我们现在知道 6 左侧（包括）的所有项都小于我们要查找到的数字（这就是为什么对数组进行排序至关重要）。
由于排除了所有这些数字，我们现在可以将其视为一个新数组，将开始位置移动到前一个中间位置的右侧，而结束位置仍然在数组的末尾。
我们以相同的方式计算中间索引：middle = (start + end) / 2 = (4 + 6) / 2 = 5。新中间索引处的数字是 9，现在大于 7。因此，我们知道 9 右侧（包括）的所有项都大于我们要查找的数字。
我们重复这个过程并创建一个新的子数组，但这次我们的末端移动到第 5 个索引的左侧。此时，我们的起点和终点索引均为 4，这意味着我们的中间索引计算为：middle = (4 + 4) / 2 = 4。
我们现在发现这个数字就是我们要找的！因此，我们从算法返回索引 4。
在 JavaScript 中实现这个算法
通常，二分搜索函数将接收两个输入：排序后的数组和目标数。通常，函数的目标是输出目标值的索引，如果找不到目标值，则输出数字 -1。
function binarySearch(array, target) {
// TBD
}
通过以上的概念回顾，我们可以看到，在整个算法中都有一个起点和终点。因此，我们可以使用 let 初始化这些值，假设它们将发生变化：
function binarySearch(array, target) {
let start = 0
let end = array.length - 1
}
接下来，我们将实现一个循环，该循环将继续将数组切成两半，直到找到正确的索引。循环不可能是无限的，所以我们需要考虑它应该何时终止。
我们在概念示例中看到，我们不能有一个大于结束索引的开始索引：
function binarySearch(array, target) {
let start = 0
let end = array.length - 1
while (start <= end) {
// TBD
}
// 如果我们走到这一步，则表明找不到目标元素，返回 -1
return -1
}
请注意，如果开始索引大于结束索引，则数组中的所有项都已排除完，并且目标根本不存在，因此返回 -1。
最后，我们可以实现算法的核心逻辑：
- 寻找中间项
- 如果中间项等于目标，则返回索引（我们找到了！）
- 如果中间项大于目标，则将结束索引移动到中间项的左侧
- 如果中间项小于目标，则将开始索引移动到中间项的右侧
const binarySearch = (arr, target) => {
let start = 0,
end = arr.length - 1
while (start <= end) {
// 找到中间索引
const middle = Math.floor((start + end) / 2)
const guess = arr[middle]
if (guess === target) return middle
if (guess > target) end = middle - 1
else start = middle + 1
}
return -1
}
binarySearch([1, 2, 3, 4, 5], 1) // 0
binarySearch([1, 2, 3, 4, 5], 5) // 4
binarySearch([1, 2, 3, 4, 5], 6) // -1
您可能已经注意到我使用 Math.floor 来计算中间索引。这是因为具有偶数项的数组没有真正的中间项，所以我们要确保有一个整数索引，而不是像 2.5 之类的索引。
计算时间复杂度
我在上面提到过，这个算法的时间复杂度是 O(log n)。这可以通过考虑您可能需要将任意列表长度 (n) 除以 2 多少次数来计算，直到只剩下一项。所以我们的方程是这样的，我们要求解 x。
1 = n / (2^x)
2^x = n
log(2^x) = log(n)
x * log(2) = log(n)
x = log(n)
更多资料
- Binary Search
- Binary Search 可视化二分搜索
本文首发 blog，如果喜欢或者有所启发，欢迎 Star，对作者也是一种鼓励。
