2rever的前端小站

二分查找的笔记

Word count: 168 / Reading time: 1 min
2018/10/12 Share
  • 递归写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function binarySearch(data, dest, start, end){
var end = end || data.length - 1,
start = start || 0,
middle = Math.floor((start + end) / 2);
// 递归完成条件
if(data[middle] == dest){
return middle;
}
// 条件判断进行不同的递归
if(dest < data[middle]){
return binarySearch(data, dest, 0, middle-1);
}else{
return binarySearch(data, dest, middle+1, end);
}

return false;
}
  • 非递归写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function binarySearch(data, dest){
var end = data.length - 1,
start = 0;
// 只要不符合条件,继续执行循环,直到不满足循环
while(start <= end){
var middle = Math.floor((end + start) / 2);
if(data[middle] == dest){
return middle;
}
if(dest > data[middle]){
start = middle + 1;
}else{
end = middle - 1;
}
}
return false;
}
CATALOG