2
在三分钟内学习二分查找
source link: https://www.51cto.com/article/777305.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
二分查找是一种在有序数组中查找元素的算法，通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。
最常见的例子是在字典中查找一个单词。假设你想找到“马拉松”的定义。你不会从字典的开头开始查找。你会打开字典大约在中间位置。如果你在‘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 <= right) {
let mid = Math.floor((left + right) / 2);
if(arr[mid] === target) return mid;
if(arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}它不仅能迅速切入数据；时间复杂度为O(logN)，比线性搜索快得多。
在空间方面，它是O(1)。不需要额外的存储空间。
小结：何时使用二分查找？
二分查找最常用于数组，但也可以应用于数据库中的有序序列、排序链表中的搜索算法，甚至决策过程中可以预测和系统地划分范围的情况。
重要的是，二分查找只能在排序的项目集合上执行。整个二分查找的方法基于这样一个原则，即集合是按顺序排列的，这样算法才能通过比较中间项来预测搜索项的位置。如果集合没有排序，这种预测就不起作用，算法也不能正确运行。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK