我用 javascript 写了一个二进制搜索。
Array.prototype.binarySearch = function(find) {
var low = 0, high = this.length - 1,
i;
while (low <= high) {
i = Math.floor((low + high) / 2);
if (this[i] > find) { low = i; continue; };
if (this[i] < find) { high = i; continue; };
return i;
}
return null;
}
虽然在我的整数数组中找不到 5,但失败了。
var intArray = [1, 2, 3, 5]
if (intArray.binarySearch(5))
alert("found!");
else
alert("no found!");
这是一个 fiddle 。 http://jsfiddle.net/3uPUF/3/
最佳答案
你有改变低和高的逻辑倒退,if this[i] > find
那么你想在 1 和 i-1 之间查找。 If this[i] < find
那么你想在 i+1 和数组的长度之间查找。
尝试进行这些更改:
Array.prototype.binarySearch = function(find) {
var low = 0, high = this.length - 1,
i;
while (low <= high) {
i = Math.floor((low + high) / 2);
if (this[i] == find) { return i; };
if (this[i] > find) { high = i - 1;};
if (this[i] < find) { low = i + 1;};
}
return null;
}
var intArray = [1, 2, 3, 5]
//index of the element in the array or null if not found
alert(intArray.binarySearch(5));
关于javascript - 为什么我的 javascript 二进制搜索出错?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9713270/