线性搜索和二分搜索有什么区别?
线性搜索和二分搜索有什么区别?
一个线性搜索逐个查看列表中的项目,不跳过任何一个。从复杂度上来说,这是一种O(n)
搜索——搜索列表所需的时间随着列表的增长而增加。
二分搜索是指从已排序的列表中间开始,看它是否大于或小于您要查找的值,从而确定该值在列表的第一半还是第二半中。然后跳到子列表的中间位置,再次进行比较等等。这基本上就是人类在字典中查找单词的方式(当然我们使用更好的启发式方法——如果你要查找“猫”,你不会从“M”开始)。从复杂度上来说,这是一种O(log n)
搜索——搜索操作的数量增长速度比列表慢,因为每次操作都将“搜索空间”减半。
例如,假设您正在A-Z字母列表(索引0-25;我们正在查找索引20处的值)中寻找U。
线性搜索会问:
list[0] == 'U'
?不是。
list[1] == 'U'
?不是。
list[2] == 'U'
?不是。
list[3] == 'U'
?不是。
list[4] == 'U'
?不是。
list[5] == 'U'
?不是。
...list[20] == 'U'
?是。完成。
二分查找会问:
将
list[12]
('M') 与 'U' 进行比较:更小,继续查找。(范围=13-25)
将list[19]
('T') 与 'U' 进行比较:更小,继续查找。(范围=20-25)
将list[22]
('W') 与 'U' 进行比较:更大,向前查找。(范围=20-21)
将list[20]
('U') 与 'U' 进行比较:找到了!完成。
对比两者:
你可以将这个过程想象成在电话簿中寻找联系人的两种不同方式。线性查找是从开始处开始,逐个读取每个姓名,直到找到目标为止。而二分查找则是打开电话簿(通常在中间),查看页面顶部的姓名,并判断你要查找的姓名是比这个姓名大还是小。如果你要查找的姓名较大,则继续按照这种方式搜索电话簿的上半部分。
线性搜索通过查看数据列表中的每个元素,直到找到目标或到达末尾。这会导致在给定列表上的O(n)性能。
二分搜索的前提是数据必须排序。我们可以利用这些信息来减少查找目标所需查看的项数。如果我们查看数据中的随机项(假设是中间项),并且该项大于我们的目标,则右侧所有项也将大于我们的目标。这意味着我们只需要查看数据的左侧部分。基本上,每次搜索目标并未命中时,我们就可以排除剩余项的一半。这为我们提供了一个很好的O(log n)时间复杂度。
请记住,即使使用最有效的算法对数据进行排序,速度也始终比线性搜索慢(最快的排序算法是O(n*log n))。因此,您不应仅仅为了执行单个二分搜索稍后再对数据进行排序。但是,如果您将执行多个搜索(至少O(log n)次搜索),则有必要对数据进行排序,以便进行二分搜索。在这种情况下,您还可以考虑其他数据结构,例如哈希表。
线性搜索从值列表的开头开始,按顺序逐个检查所寻找的结果。
二分搜索从排序数组的中间开始,并确定您要查找的值在哪一侧(如果有)。然后,以相同的方式再次搜索该“半”数组,每次将结果减半两次。
请务必仔细考虑,是否值得为了使用二分查找而保持列表排序(即使这样做的代价很高)。例如,如果您需要频繁进行插入/删除操作,但只偶尔进行搜索,则总体而言,二分查找可能比线性查找更慢。
线性搜索,也称为顺序搜索,按照顺序从开始的每个元素开始查看数据结构中是否存在所需的元素。当数据量很小时,这种搜索会很快。它很容易但需要搜索的数据量与工作量成正比。如果所需的元素不存在,则元素数量加倍将使搜索时间加倍。
二分搜索对于较大的数组效率更高。我们检查中间元素。如果该值大于我们正在查找的值,则在第一半中查找;否则,在第二半中查找。重复此过程直到找到所需的项。二分搜索需要对表进行排序。它每次迭代都会减少一半的数据,因此具有对数级别的复杂度。
如果要搜索1000个元素,则二分搜索需要约10步,线性搜索需要1000步。
二分查找的时间复杂度是O(logn),而线性查找的时间复杂度是O(n),因此二分查找具有更好的性能。
var unsortedhaystack = [];
var haystack = [];
function init() {
unsortedhaystack = document.getElementById("haystack").value.split(' ');
}
function sortHaystack() {
var t = timer('sort benchmark');
haystack = unsortedhaystack.sort();
t.stop();
}
var timer = function(name) {
var start = new Date();
return {
stop: function() {
var end = new Date();
var time = end.getTime() - start.getTime();
console.log('Timer:', name, 'finished in', time, 'ms');
}
}
};
function lineerSearch() {
init();
var t = timer('lineerSearch benchmark');
var input = this.event.target.value;
for(var i = 0;i<unsortedhaystack.length - 1;i++) {
if (unsortedhaystack[i] === input) {
document.getElementById('result').innerHTML = 'result is... "' + unsortedhaystack[i] + '", on index: ' + i + ' of the unsorted array. Found' + ' within ' + i + ' iterations';
console.log(document.getElementById('result').innerHTML);
t.stop();
return unsortedhaystack[i];
}
}
}
function binarySearch () {
init();
sortHaystack();
var t = timer('binarySearch benchmark');
var firstIndex = 0;
var lastIndex = haystack.length-1;
var input = this.event.target.value;
//currently point in the half of the array
var currentIndex = (haystack.length-1)/2 | 0;
var iterations = 0;
while (firstIndex <= lastIndex) {
currentIndex = (firstIndex + lastIndex)/2 | 0;
iterations++;
if (haystack[currentIndex] < input) {
firstIndex = currentIndex + 1;
//console.log(currentIndex + " added, fI:"+firstIndex+", lI: "+lastIndex);
} else if (haystack[currentIndex] > input) {
lastIndex = currentIndex - 1;
//console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex);
} else {
document.getElementById('result').innerHTML = 'result is... "' + haystack[currentIndex] + '", on index: ' + currentIndex + ' of the sorted array. Found' + ' within ' + iterations + ' iterations';
console.log(document.getElementById('result').innerHTML);
t.stop();
return true;
}
}
}