javascript 二分法(數組array)
2024-05-06 14:10:23
供稿：網友
在Javascript中，我們可以通過prototype關鍵字為對象添加新的屬性或者是方法，下面是一個為Array對象添加二分法查找功能的方法：
代碼如下:
Array.prototype.binarySearch = function(obj)
{
var value = 0;
var left = 0;
var right= this.length;
while(left <= right)
{
var center = Math.floor((left+right)/2);
if(this[center] == obj)
{
value = center;
}
if(obj < this[center])
{
right = center - 1;
}
else
{
left = center + 1;
}
}
alert(value);
}
//如下為測試代碼：
function testArrayBinarySearch()
{
var array = new Array();
var key = 678;
var number = 1000;
for (i = 0; i < number; i++)
{
array.push(i);
}
array.binarySearch(key);
}
window.onload = function()
{
testArrayBinarySearch();
}
下面是國外的代碼
javascript二分法 //Copyright 2009 Nicholas C. Zakas. All rights reserved.
//MIT-Licensed, see source file
代碼如下:
function binarySearch(items, value){
var startIndex = 0,
stopIndex = items.length - 1,
middle = Math.floor((stopIndex + startIndex)/2);
while(items[middle] != value && startIndex < stopIndex){
//adjust search area（調整查找范圍）
if (value < items[middle]){
stopIndex = middle - 1;
} else if (value > items[middle]){
startIndex = middle + 1;
}
//recalculate middle（重新計算中項索引）
middle = Math.floor((stopIndex + startIndex)/2);
}
//make sure it's the right value（確保返回正確的值）
return (items[middle] != value) ? -1 : middle;
}
