如何在JavaScript中实现二进制搜索
How to implement binary search in JavaScript
https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/p/challenge-binary-search
我按照伪代码在链接上实现算法,但不知道我的代码出了什么问题。
这是我的代码:
/* Returns either the index of the location in the array,
or -1 if the array did not contain the targetValue */
var doSearch = function(array, targetValue) {
var min = 0;
var max = array.length - 1;
var guess;
while(min < max) {
guess = (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];
var result = doSearch(primes, 2);
println("Found prime at index " + result);
//Program.assertEqual(doSearch(primes, 73), 20);
要从数组中获取值,需要指定一个整数,如array[1]
。在您的情况下,array[1.25]
将返回undefined
。
为了让它发挥作用,我只是在循环中添加了Math.floor
,以确保我们得到一个整数。
编辑:正如@KarelG指出的,您还需要在while循环中添加<=
。这是针对min
和max
已经变得相同的情况,在这种情况下为guess === max === min
。如果没有<=
,循环将不会在这些情况下运行,并且函数将返回-1
。
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;
}
您可以使用Math.floor
、Math.ceil
和Math.round
中的任何一个。
我希望这是一个小帮助,我不太善于解释,但我会尽我所能详细说明。
在代码中,当min等于max时,循环结束。但在这种情况下,您没有检查array[min] == targetValue
因此,将代码更改为这样很可能会解决您的问题
/* Returns either the index of the location in the array,
or -1 if the array did not contain the targetValue */
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;
};
JSFiddle链接:http://jsfiddle.net/7zfph6ks/
希望能有所帮助。
PS:代码中唯一的变化是这一行:while (min <= max)
您只需取消对Program.assertEqual的注释像这样:
Program.assertEqual(doSearch(primes, 73), 20);
不是这样的:
//Program.assertEqual(doSearch(primes, 73), 20);
如果有人仍在寻找答案,您需要将其设置为(max>=min)
while (max >= min) {
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;
相关文章:
- 如何使用动画实现纸张推车
- 客户端服务器REST API captcha实现
- 如何实现此布局
- 如何将PDF作为二进制文件传递到window.open()
- 如何将字母转换为二进制代码
- Meteor忘记了密码的实现
- 使用Native Sockets在Android中实现WebSockets
- 在样板文件中实现Ajax
- instanceof是如何在JavaScript中实现的
- 如何正确实现Jquery多选小部件
- 实现一个建立在google.com之上的自定义搜索引擎
- 多个组件是如何实现的
- window.location使用jquery mobile实现chrome跳转
- 如何在OpenERP中实现网络摄像头
- 如何在JavaScript中实现二进制搜索
- 二进制数据的可移植hashCode实现
- JavaScript实现的打印二进制树的左视图返回错误的结果
- JavaScript中的二进制搜索实现
- 我可以得到反馈我失败的二进制搜索实现
- 为什么这个二进制搜索实现会使浏览器无响应?