用javascript实现二分查找

二分查找又称折半查找，顾名思义就是一半半的查找。另外二分查找的列表需要为有序列表。

思路：
1）定义左边界下标，右边界下标，中间数字下标
2）当左边界下标不大于右边界下标时（这个等价于“小于等于”，有点拗口）
2-1 如果查找到的数比目标数要大则以此中间数字下标-1为右边界，跳到2）
2-2 如果查找到的数比目标数要小则以此中间数字下标+1为左边界，跳到2）
2-3 如果找到目标数字，直接返回，结束
3）返回-1，表示无法查找到

然后是代码：

var binarySearch=function(arr,key){

  // 定义左边界下标，右边界下标，中间数字下标
  var left=0;
  var right=arr.length-1;
  var mid;

  while(left<=right){
    mid=parseInt((left+right)/2);

    if(arr[mid]>key){
      // 如果查找到的数比目标数要大，则以此中间数字下标-1为右边界
      right=mid-1;
    }else if(arr[mid]<key){
      // 如果查找到的数比目标数要小，则以此中间数字下标+1为左边界
      left=mid+1;
    }else{
      // 如果找到目标数字，直接返回，结束
      return mid;
    }
  }

如果是C语言，left和high在很大的时候可能会发生溢出的情况（mid为负数）。但是javascript似乎没有这个问题，因此这里不讨论。

然后是测试用例，我们就用一个循环来判断每次查找是否正确。
假设数组为1 2 3 4 5 6 7 8 9 10 11
那么：
查找1，输出1
查找2，输出2
……
查找11，输出11
查找12，输出undefined

var testArr=[1,2,3,4,5,6,7,8,9,10,11];
var result;
for(var i=0;i<testArr.length;i++){
  result=binarySearch(testArr,testArr[i]);
  console.log(testArr[result]);
}
result=binarySearch(testArr,12);
console.log(testArr[result]);

结果

1
2
3
4
5
6
7
8
9
10
11
undefined

测试通过。应该没有问题。

然后是最差情况下的时间复杂度的问题。
假设现在数据规模为N
第一次折半后数据规模为N/2^1
第二次折半后数据规模为N/2^2
第三次折半后数据规模为N/2^3
第M此折半后数据规模为N/2^M，而此时，数据规模为1，假设查找不到，跳出
因此最差的情况下，查找了M+1次
N/2^M=1则M=lg(N)
所以O(n)=M+1=lg(N)+1=lg(N)
log以2为底。