在三分钟内学习二分查找

二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。

最常见的例子是在字典中查找一个单词。假设你想找到“马拉松”的定义。你不会从字典的开头开始查找。你会打开字典大约在中间位置。如果你在‘T’处,你已经过头了。所以,你会调整并分割差距,缩小范围直到找到“马拉松”。

这个逐步排除的过程就是二分查找的要点,但是针对数组的情况。

线性查找 vs 二分查找

考虑一个从1到100的数字数组,你需要在这个范围内找到一个特定的数字,就像玩一个猜数游戏。

线性查找

简单的方法是使用一个简单的for循环——遍历数组中的每个元素直到找到目标项。

function findItem(arr, item) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === item) {
return i;
}
}
return -1; // 未找到项
}

这个方法可以找到,但它的时间复杂度是O(n);想象一下,如果你要找的数在1到1万亿之间。

你可以比线性查找做得更好。

二分查找

使用二分查找,不是检查每个元素,而是从中间开始。如果你要找的数字更大,你向右走;如果更小,你向左走。

然后呢?你重复这个过程。中间,左边或右边,缩小可能性直到找到数字。

function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while(left