我有一个具有 1,000 个或更多值(可能高达 5000+)的已排序整数数组。我需要编写一个函数,它接收一个 int 并根据数组中的元素返回一个 bool。我知道我可以编写一个带中断的 for 循环,我知道我可以使用 jquery .InArray。
实现这一点的最佳方法是什么,知道数组已排序。
谢谢。
我有一个具有 1,000 个或更多值(可能高达 5000+)的已排序整数数组。我需要编写一个函数,它接收一个 int 并根据数组中的元素返回一个 bool。我知道我可以编写一个带中断的 for 循环,我知道我可以使用 jquery .InArray。
实现这一点的最佳方法是什么,知道数组已排序。
谢谢。
知道数组已排序,二进制搜索将是最好的方法。
我认为您想使用二进制搜索例程。二进制搜索例程是,而线性搜索平均而言是.
选择形式有很多变化。这是我在这篇文章中找到的一个:
function binarySearch(items, value){
var startIndex = 0,
stopIndex = items.length - 1,
middle = Math.floor((stopIndex + startIndex)/2);
while(items[middle] != value && startIndex < stopIndex){
//adjust search area
if (value < items[middle]){
stopIndex = middle - 1;
} else if (value > items[middle]){
startIndex = middle + 1;
}
//recalculate middle
middle = Math.floor((stopIndex + startIndex)/2);
}
//make sure it's the right value
return (items[middle] != value) ? -1 : middle;
}
或者这篇文章中这个看起来更简单的版本,它具有无数种不同语言的二进制搜索功能。
function binary_search_iterative(a, value) {
var lo = 0, hi = a.length - 1, mid;
while (lo <= hi) {
mid = Math.floor((lo+hi)/2);
if (a[mid] > value)
hi = mid - 1;
else if (a[mid] < value)
lo = mid + 1;
else
return mid;
}
return null;
}
Google 闭包中还有一个二分搜索,这里的代码。
并且,很好地描述了二进制搜索算法在Wikipedia上的工作原理。
如果数组已排序,则答案已排序 - 使用二进制印章。
如果进行多次查找,请迁移到类似地图的对象。
var fastLookup = {};
mySortedArray.forEach(function(i){fastLookup[i]=true)});
//Each time:
if (fastLookup[key]===true){ //do thing
}
许多语言已经实现了这个,例如在 java 中你可以使用 CollectionsCollections.binarySearch(List> list, T key) 方法,我很确定 C# 也有某种 BinarySearch 方法。