Javascript 折半搜索法（二分法）

发表于   |   分类于   |     |   阅读次数

周末，写个简单的算法。

JS二分法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Array.prototype.binarySearch = function (v) {
	var l = 0;
	var h = this.length - 1;
	while (l<= h) {
		var m = l + ((h - l) >> 1);
		console.log('l@%s,h@%s,m@%s', l, h, m);
		if (this[m] === v) {
			return m;
		}
		if (this[m] > v) {
			h = m - 1;
		} else {
			l = m + 1;
		}
	}
	return -(l + 1);
}

使用：

1
2
3
4
5
6
7
var arr = [1, 2, 3, 5, 78, 2312, 424];
arr.sort(function (x, y) {
	return x - y;
})
console.log(arr);
console.log(arr.binarySearch(424));

说明：

var m = l + ((h - l) >> 1);，为什么要用位运算？

其实用var m = Math.floor((h+l)/2);也是可以的，但是位运算的速度优于除法，并且还要再进行一次Math.floor。用位运算主要是出于性能考虑。h+l还存在溢出的问题，不过这个在web端应该不会遇到。。。Node.js就有可能了。

还有个复杂度的问题，下回再分析。

伊泽
2013-07-29于杭州