可汗学院算法：二分查找解决方案

Question

我在 Khan Academy 学习算法：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

我错过了什么？

- Sathish

---

@JoachimPileborg，您说的“您确定吗？”是什么意思？为什么我被踩了？我只是在按照这个fiddle http://jsfiddle.net/7zfph6ks/ 的示例进行操作。 - Sathish

@JoachimPileborg 不是吗？看起来是这样的。 - Evan Knowles

@JoachimPileborg 这是真的吗？你能给我指出一个正确的求平均值的表达式吗？ - Sathish

我显然还没有清醒过来。对于造成的困惑，我感到抱歉。 - Some programmer dude

这里的问题不在于效率，而在于正确性。 - Scott Hunter

Answer 1

你提前终止了循环 - 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

- Evan Knowles

Answer 2

假设您的列表只有2个质数，并且您正在寻找更大的那个。您的循环将针对较小值进行测试，失败并将min设置为与max相同，因此循环将在检查该值之前终止。

您的循环保护应该是min <= max。

- Scott Hunter