确定元素是否在排序数组中的最快方法

Question

我有一个具有1,000或更多值（可能高达5000+）的排序整数的数组。我需要编写一个接收int的函数，并根据数组中的元素返回一个bool。我知道我可以用break来写一个for循环，我知道我可以使用jQuery .InArray。

什么是最好的方式来实现这一点，知道该数组排序。

谢谢。

Answer 1

知道该数组是排序二进制搜索将是最好的方法。

Answer 2

如果数组的排序，那么答案的排序 - 使用二进制排序。

Answer 3

我想你会想使用二进制搜索例程。二进制搜索例程是，而线性搜索的平均值为。

选择表单有很多变化。这里有一个我在this article发现：

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; 
} 

或者从this article已经在无数个不同语言的二进制搜索功能，这更简单的看的版本。

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; 
} 

在谷歌关闭中还有一个二进制搜索，代码为here。

而且，对二进制搜索算法如何工作的一个很好的描述Wikipedia。

Answer 4

许多语言已经在java中实现了，例如你可以使用CollectionsCollections.binarySearch（List> list，T key）方法，我非常确定C＃也有某种BinarySearch方法。

Answer 5

如果多次执行查找，请迁移到类似地图的对象。

var fastLookup = {}; 
 
mySortedArray.forEach(function(i){fastLookup[i]=true)}); 
 

 
//Each time: 
 
    if (fastLookup[key]===true){ //do thing 
 
    }