二分查找

二分查找算法，又叫折半查找。
听名字，二分，就是一分为二，从中间分开，然后找出符合自己要求的值；回溯到之前位置，重复即可。只看文字，是不是有点懵逼，那就直接看下代码吧：

int binary_search(int *arr, int n, int x) {
      int head = 0, tail = n - 1, mid;
      while(head <= tail) {
             mid = (head + tail) >>1;
             if(arr[mid] == x) return mid; 
             if(arr[mid] > x)  head = mid + 1;
             else tail = mid - 1;
     }
     return -1;
}

看下代码，是不是很简洁了。每一行都是很有意义的。理解完了，换成函数的方式看下：

int binary_search(int (*arr)(int), int n, int x) {
      int head = 0, tail = n - 1, mid;
      while(head <= tail) {
             mid = (head + tail) >>1;
             if(arr(mid) == x) return mid; 
             if(arr(mid) > x)  head = mid + 1;
             else tail = mid - 1;
     }
     return -1;
}

这个是c语言的函数的方式实现的。理解下函数式编程，我第一次也写错了；后来看到错误，就知道怎么回事了！
好了，今天到此结束。

12.7 更新排版