爲什麼我的javascript二進制搜索錯誤？

Question

我在javascript中編寫了一個二進制搜索。

Array.prototype.binarySearch = function(find) { 
    var low = 0, high = this.length - 1, 
     i; 
    while (low <= high) { 
    i = Math.floor((low + high)/2); 
    if (this[i] > find) { low = i; continue; }; 
    if (this[i] < find) { high = i; continue; }; 
    return i; 
    } 
    return null; 
} 

雖然在我的整數數組中找到5，但它失敗了。

var intArray = [1, 2, 3, 5] 

if (intArray.binarySearch(5)) 
    alert("found!"); 
else 
    alert("no found!"); 

這是一個小提琴。 http://jsfiddle.net/3uPUF/3/

Answer 1

你有邏輯向後改變低和高，if this[i] > find然後你想看看1和i-1之間。 If this[i] < find然後你想看看i + 1和數組的長度。

嘗試做了這些改變：

Array.prototype.binarySearch = function(find) { 
    var low = 0, high = this.length - 1, 
     i; 
    while (low <= high) { 
    i = Math.floor((low + high)/2); 
    if (this[i] == find) { return i; }; 
    if (this[i] > find) { high = i - 1;}; 
    if (this[i] < find) { low = i + 1;}; 
    } 
    return null; 
} 

var intArray = [1, 2, 3, 5] 
//index of the element in the array or null if not found  
alert(intArray.binarySearch(5)); 

在撥弄

Answer 2

你的比較是倒退的。如果在i找到的物品大於您要查找的物品，那麼您要調整high，而不是low。請參閱我的updated jsFiddle。