javascript 二分法(数组array)

269 阅读 0 评论 178 点赞

我是靠谱客的博主健壮蓝天，最近开发中收集的这篇文章主要介绍javascript 二分法(数组array)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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