在很早之前，我就写过了一篇也关于二分法的相关博文：JavaScript快排与原生sort的测试。当时是用二分法进行快速排序，其实和这次思路大致相当。二分查找最重要的一个条件，就是需要将数组先按照从小到大的顺序进行排序后，方可进行查找。
一起来想想大致的思路：
1
2
3
4
| 1. binarySearch函数需要接收的参数是：一个预先排序好的数组，一个需要查找的目标值，左边界和右边界。
2. 让数组的中值和目标值比较，若相等，则返回中值所在的序号，函数结束。若不相等，进行第三步
3. 不相等，则进行大小比较，若目标比中值小，则范围缩小到左边界到中值，并重新返回第一步。反之，范围缩小到中值到右边界，返回第一步。
4. 找不到则是，中值序号等于左边界或右边界，返回-1。
|
这个伪代码，写的还是有点凌乱的。最主要的思想还是在于递归。一起实现上述的代码吧。我用的是coffeeScript实现的，除了某些地方我会指出来，大致都能看懂的。若对coffeeScript感兴趣的同学，可以移步：CoffeeScript中文。还是要强调一下，coffee的块级判断是靠缩进层次的。所以使用时，千万不要空格和Tab缩进混用。
1
2
3
4
5
6
7
8
9
10
11
12
13
| binarySearch = (dataArr, target, start = 0, end = dataArr.length-1)->
# 若不传参，参数默认: start = 0, end = dataArr.length - 1
middle = parseInt((start + end) / 2) # 取中间序号
return -1 if middle == start or middle == end # 查询失败
if(dataArr[middle] == target)
return middle # 查询成功
if(target < dataArr[middle])
return binarySearch(dataArr, target, 0, middle-1)
else
return binarySearch(dataArr, target, middle+1, end)
|
想一下，为了某些没用过Coffee的同学，还是把它编译出来的Js也一同放上吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| var binarySearch = function(dataArr, target, start, end) {
var middle;
if (start == null) {
start = 0;
}
if (end == null) {
end = dataArr.length - 1;
}
middle = parseInt((start + end) / 2);
if (middle === start || middle === end) {
return -1;
}
if (dataArr[middle] === target) {
return middle;
}
if (target < dataArr[middle]) {
return binarySearch(dataArr, target, 0, middle - 1);
} else {
return binarySearch(dataArr, target, middle + 1, end);
}
};
|
