javascript 可汗学院算法：二分搜索解决方案
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/30567593/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Khan academy Algorithm: Binary Search Solution
提问by Sathish
I was working towards algorithms in khan academy : https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/p/challenge-binary-searchMost of the code below results in -1 ? Why is that? So Binary Search Wont work Efficiently ?
我在可汗学院研究算法：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);
}
Results:
结果：
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
What am i missing?
我错过了什么？
回答by Evan Knowles
You are terminating the loop too early - min == maxis a valid condition.
您过早终止循环 -min == max是有效条件。
Change your loop to
将您的循环更改为
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;
}
}
I get an output of
我得到一个输出
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
回答by Scott Hunter
Suppose your list had just 2 primes, and you search for the larger. Your loop will test against the smaller, fail, and set minto be the same as max, so the loop will terminate before ever checking that value.
假设您的列表只有 2 个素数，并且您搜索较大的素数。您的循环将针对更小、失败和设置min为与 相同的 进行测试max，因此循环将在检查该值之前终止 。
Your loop guard should be min <= max.
你的循环守卫应该是min <= max.
