確定元素是否在排序數組中的最快方法

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 
 
    }