人气排行榜三分钟学习二分查找
文章编号：1375 /
更新时间：2023-12-22 15:32:02 / 浏览：次
相关标签： 二分查找、
二分查询是一种在有序数组中搜索元素的算法，通过将搜索区域分割为两半来实现。你可能在日常生活中已经不经意地使用了大脑里的二分查询。
最常见的例子是在字典中搜索一个单词。假设你想找到马拉松的定义。你不会从字典的开头开始搜索。你会打开字典大约在中间位置。如果你在‘T’处，你已经过头了。所以，你会调整并分割差距，缩小范围直到找到马拉松。
这个逐步排除的过程就是二分查找的关键，但是针对数组的情况。
线性查找vs二分查询
考虑一个从1到100的数字数组，你需要在这个范围内搜索一个特定的数字，就像玩一个猜数游戏。
线性查找
简单的方法是使用一个简单的for循环——遍历数组中的每个元素直到找到目标项。
functionfindItem(arr,item){for(leti=0;i这个可以找到，但它的时间复杂度是O(n)；想象一下，如果你要找的数在1到1万亿之间。
你可以比性查找做得更好。
二分查询
使用二分查找，不是检查每个元素，而是从中间开始。如果你要找的数字更大，你向右走；如果更小，你向左走。
然后呢？你重复这个过程。中间，左边或右边，缩小可能性直到找到数字。
functionbinarySearch(arr,target){letleft=0;letright=arr.length-1;while(left<=right){letmid=Math.floor((left+right)/2);if(arr[mid]===target)returnmid;if(arr[mid]它不仅能迅速进入数据；时间复杂度为O(logN)，比线性搜索快得多。
在空间方面，它是O(1)。不需要额外的存储空间。
小结：何时使用二分查找？
二分查找最常用于数组，但也可以应用于数据库中的有序序列、排序链表中的搜索算法，甚至决策过程中可以预测和系统地划分范围的情况。
重要的是，二分查找只能在排序的项目集合上执行。整个二分查找的方法基于这样一个原则，即集合是按顺序排列的，这样算法才能通过比较中间项来预测搜索项的位置。如果集合没有排序，这种预测就不起作用，算法也不能正确运行。
相关标签： 二分查找、
本文地址：https://www.rixiy.com/article/ef1525859979e55c2842.html
做上本站友情链接,在您站上点击一次,即可自动收录并自动排在本站第一位！
<a href="https://www.rixiy.com/" target="_blank">日夕导航</a>
<a href="https://www.rixiy.com/" target="_blank">日夕导航</a>
