汗學院算法：二進制搜索解決方案

我正在努力在可汗學院的算法： https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/p/challenge-binary-search 以下大部分代碼的結果爲-1？這是爲什麼？所以二進制搜索不會有效地工作？汗學院算法：二進制搜索解決方案

var doSearch = function(array, targetValue) { 
    var min = 0; 
    var max = array.length - 1; 
    var guess; 

    while(min < max) { 
     guess = Math.floor((max + min)/2); 

     if (array[guess] === targetValue) { 
      return guess; 
     } 
     else if (array[guess] < targetValue) { 
      min = guess + 1; 
     } 
     else { 
      max = guess - 1; 
     } 

    } 

    return -1; 
}; 

var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
     41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]; 

for(var i=0;i<primes.length;i++){ 
    var result = doSearch(primes,primes[i]); 
    console.log("Found prime at index of " + primes[i] +" @ " + result);  
}

結果：

Found prime at index of 2 @ 0 
Found prime at index of 3 @ -1 
Found prime at index of 5 @ 2 
Found prime at index of 7 @ 3 
Found prime at index of 11 @ -1 
Found prime at index of 13 @ 5 
Found prime at index of 17 @ 6 
Found prime at index of 19 @ -1 
Found prime at index of 23 @ 8 
Found prime at index of 29 @ -1 
Found prime at index of 31 @ 10 
Found prime at index of 37 @ -1 
Found prime at index of 41 @ 12 
Found prime at index of 43 @ 13 
Found prime at index of 47 @ -1 
Found prime at index of 53 @ 15 
Found prime at index of 59 @ 16 
Found prime at index of 61 @ -1 
Found prime at index of 67 @ 18 
Found prime at index of 71 @ 19 
Found prime at index of 73 @ -1 
Found prime at index of 79 @ 21 
Found prime at index of 83 @ -1 
Found prime at index of 89 @ 23 
Found prime at index of 97 @ -1

我失去了什麼？

來源

2015-06-01 Sathish

@JoachimPileborg你確定是什麼意思？爲什麼我投票呢？我跟着這個小提琴http://jsfiddle.net/7zfph6ks/ – Sathish

@JoachimPileborg不是嗎？它似乎。 –

@JoachimPileborg是這樣嗎？你能指出我的平均表現嗎？ – Sathish

您正在終止迴路太早 - min == max是一個有效的條件。

你的循環改爲

while(min <= max) { 
    guess = Math.floor((max + min)/2); 

    if (array[guess] === targetValue) { 
     return guess; 
    } 
    else if (array[guess] < targetValue) { 
     min = guess + 1; 
    } 
    else { 
     max = guess - 1; 
    } 

}

我得到的

VM153:30 Found prime at index of 2 @ 0 
VM153:30 Found prime at index of 3 @ 1 
VM153:30 Found prime at index of 5 @ 2 
VM153:30 Found prime at index of 7 @ 3 
VM153:30 Found prime at index of 11 @ 4 
VM153:30 Found prime at index of 13 @ 5 
VM153:30 Found prime at index of 17 @ 6 
VM153:30 Found prime at index of 19 @ 7 
VM153:30 Found prime at index of 23 @ 8 
VM153:30 Found prime at index of 29 @ 9 
VM153:30 Found prime at index of 31 @ 10 
VM153:30 Found prime at index of 37 @ 11 
VM153:30 Found prime at index of 41 @ 12 
VM153:30 Found prime at index of 43 @ 13 
VM153:30 Found prime at index of 47 @ 14 
VM153:30 Found prime at index of 53 @ 15 
VM153:30 Found prime at index of 59 @ 16 
VM153:30 Found prime at index of 61 @ 17 
VM153:30 Found prime at index of 67 @ 18 
VM153:30 Found prime at index of 71 @ 19 
VM153:30 Found prime at index of 73 @ 20 
VM153:30 Found prime at index of 79 @ 21 
VM153:30 Found prime at index of 83 @ 22 
VM153:30 Found prime at index of 89 @ 23 
VM153:30 Found prime at index of 97 @ 24

來源

2015-06-01 07:20:39

哦，我沒有注意到。謝謝！！ – Sathish

輸出假設你的名單剛剛2素數，而你搜索越大。您的循環將針對較小的失敗進行測試，並將min設置爲與max相同，因此在檢查該值之前，循環將終止。

你的環衛應該是min <= max。

來源

2015-06-01 10:41:23

汗學院算法：二進制搜索解決方案

回答

相關問題