介绍：
在计算机科学中，折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。 搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的 那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
时间复杂度
折半搜索每次把搜索区域减少一半，时间复杂度为O(logN)。（N代表集合中元素的个数）
空间复杂度
O(1)，虽以递归形式定义，但是尾递归，可改写为循环。
测试结果：
数组里有500000个随机数, 执行500次后花费的毫秒数
最大毫秒数为21
最小毫秒数为1
平均毫秒数为2
代码示例：
<!doctype html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>二分查找算法</title>
</head>
<body>
<script>
var count = 10000,
num = testCount = 500,
i,
exeCount,
exeTimeArr = [],
binarySearch = function(n, a, lastIndex, type){
if(a.length === 0) return -1;
lastIndex = lastIndex || 0;
var middle = Math.floor(a.length / 2),
thisIndex = middle;
if(type == 'right'){
thisIndex = lastIndex + middle + 1;
}else if(type == 'left'){
thisIndex = lastIndex - ( a.length - middle);
}
if(a[middle] === n){
return thisIndex;
}else{
if(n > a[middle]){
return binarySearch( n, a.slice(middle + 1), thisIndex, 'right' );
}else{
return binarySearch( n, a.slice(0, middle), thisIndex, 'left' );
}
}
};
var body = document.getElementsByTagName('body')[0];
var log = function(s){
var p = document.createElement('p');
var ps = document.getElementsByTagName('p');
p.innerHTML = s;
ps.length ?
body.insertBefore(p, ps[0]) :
body.appendChild(p);
//document.write(s + '<br />'); 破坏文档结构
//firefox下使用console.log并开启firebug会影响执行
}
function exeTest( callback ){
function test(){
var cost,
startTime,
arr = [],
index,
num = Math.round(Math.random() * count);
testCount--;
// 构建随机数组
for(i=0;i<count;i++){
arr.push( Math.round(Math.random() * count) ); // 0 - count
}
arr.sort(function(a, b){
return a - b;
});
startTime = + new Date();
// 算法执行
index = binarySearch( num, arr );
exeTimeArr.push(cost = new Date() - startTime); //花费的毫秒数
log('本次测试花费 '+ cost +' 毫秒, 还剩 '+ testCount +' 次测试, 该数的index为 ' + index);
if(testCount == 0 && typeof callback == 'function'){
callback();
}else{
// 预防浏览器挂起
setTimeout(test, 0);
}
}
test();
}
function callback(){
var sum = 0;
var result = '数组里有'+ count +'个随机数, 执行'+ num +'次后花费的毫秒数' + '<br />' +
'最大毫秒数为' + Math.max.apply(null, exeTimeArr) + '<br />' +
'最小毫秒数为' + Math.min.apply(null, exeTimeArr) + '<br />';
exeTimeArr.forEach(function(value) {
sum += value;
})
result += '平均毫秒数为' + Math.round( sum / num ) ;
log(result);
}
// 开始测试
exeTest(callback);
</script>
</body>
</html>
