汗学院算法：二进制搜索解决方案

我正在努力在可汗学院的算法： 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

汗学院算法：二进制搜索解决方案

回答

相关问题