如何在JavaScript中实现二进制搜索 [英] How to implement binary search in JavaScript
问题描述
我正在遵循伪代码来实现链接上的算法,但不知道我的代码有什么问题。
这是我的代码:
/ *返回数组中位置的索引,
或-1如果数组不包含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;
}
}
返回-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(在索引处找到素数+结果);
//Program.assertEqual(doSearch(primes,73),20);
要从数组中获取值,您需要指定像 array [1]
这样的整数。 array [1.25]
将在您的情况下返回 undefined
。
<为了让它正常工作,我只需在你的循环中添加
Math.floor
,以确保我们得到一个整数。 编辑:作为@KarelG pointet,您还需要在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;
}
}
返回-1;
}
您可以使用 Math.floor
, Math.ceil
, Math.round
。
我希望这是一个很小的帮助,我不是很擅长解释,但我会做的就是详细说明。
I was following the pseudo code to implement algorithm on the link but don't know what's wrong with my code.
Here is my code :
/* 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);
To get a value from an array you need to specify a whole number like array[1]
. array[1.25]
will return undefined
in your case.
To get it working I simply added Math.floor
inside you loop to insure we get a whole number.
EDIT: As @KarelG pointet out you also need to add <=
in your while loop. This is for situations where min
and max
have become the same, in which case guess === max === min
. Without the <=
the loop would not run in these situations and the function would return -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;
}
You could use either of Math.floor
, Math.ceil
, and Math.round
.
I hope this was a small help, I am not very good at explaining, but I'll do my be to elaborate.
这篇关于如何在JavaScript中实现二进制搜索的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!