找到範圍在陣列

Question

最有效的方法我有整數編號的排序後的數組，可以是正的負：

[ -30, -13, -10, -4, -1, 4, 23, 55, 90, 234, 433, 500 ] 

我需要找到大於或等於零的最低數目的索引並且最大的數字小於或等於400.
什麼是最有效的方法呢？
（我正在使用JavaScript，但任何語言或僞代碼都可以）

Answer 1

O(log N)

的jsfiddle：這裏http://jsfiddle.net/vCY68/

function binaryIndexOf(data, criteria) { 
    'use strict'; 

    var minIndex = 0; 
    var maxIndex = data.length - 1; 
    var currentIndex; 
    var currentElement; 
    var result = null; 

    while (minIndex <= maxIndex) { 
     currentIndex = (minIndex + maxIndex)/2 | 0; 
     currentElement = data[currentIndex]; 
     var comparison = criteria(currentElement); 

     if (comparison[0] == 'right') { 
      minIndex = currentIndex + 1; 
     } else { 
      maxIndex = currentIndex - 1; 
     } 

     if (comparison[1]) { 
      result = currentIndex; 
     } 
    } 

    return result; 
} 

var firstPositive = binaryIndexOf(data, function(value) { 
    return value < 0 ? ['right', false] : ['left', true]; 
}); 

var lastLess400 = binaryIndexOf(data, function(value) { 
    return value > 400 ? ['left', false] : ['right', true]; 
}); 

比較函數返回2個值：第一是，其中該比較後移動。第二是如果當前值是可以接受的。

PS：保存時間上執行二進制搜索從http://oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/代碼被取出，用較小的修改

PPS：潛在地可以指定是否初始化搜索範圍手動減少比較的數量和參數與所述第二搜索firstPositive + 1開始索引

Answer 2

在數組中執行二進制搜索0和400。如果你點擊0或者400，那麼這就是答案，否則檢查你到達的數組元素以及左側或右側的元素，看看哪個最大小於0或者最大小於400.複雜度是O（日誌n）如果你的數組大小爲n。

Answer 3

對數組中大於0的最小元素和大於400的最大元素執行二分搜索。

如果您的索引旁邊的元素仍在減少或增加，您需要在搜索中稍做修改才能每次檢查。例如：如果你達到3，前一個元素是-2，那麼3將是你的答案（即，而不是比較你的平等，你正在尋找下一個最高或最低值）

你將需要2 O （logn）操作來實現這一點。