DIV CSS 佈局教程網

為 Array 擴展二分法查找
編輯:關於JavaScript     

在 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();
}

這版代碼有兩個問題值得指出

一是右邊界初始化為 this.length,但合法下標最大只能是 length - 1,這裡會越界一格;二是找到目標後並沒有 break,循環還會繼續跑下去,多說明了效率上的浪費。另外,二分查找的前提是數組有序,而這個方法本身並未做任何檢查。

另一份實現:Nicholas C. Zakas 版本

國外還流傳著一份更嚴謹的實現:


復制代碼 代碼如下:
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;
}

這一版的優點很清楚:右邊界用的是 length - 1,不會越界;循環條件把「找到」和「區間收縮完」兩種終止情況都照顧到了;最後用 -1 表示未找到,也比前者的 alert(value) 更適合被其他代碼調用。

順帶說一句,直接修改 Array.prototype 這種做法在現代開發中並不推薦——一旦與其他庫或團隊代碼發生命名衝突,排查起來會非常痛苦。更穩妥的方式是寫成獨立工具函數。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved