再回首之二分查找

本来觉得这是一个很简单，简单到入门必会的东西。

可是。但是现在却有了新的认识。

家里余粮不多，最近找米，有卖家问了个问题。你给写下二分查找

我心想，这么so easy的问题也问吗？

但是还是按规矩来写。一写不要紧。折磨了6，7分钟。总算是写出来，自己不满意，感觉有问题。

回来好好想想。这个问题确实考察了很多。

迭代实现，非递归

int binSearchNR(int * arr, int low, int high, int key){ if(!arr) return -1; int left = low, right = high; while(left <= right) { //int mid=(left+right)/2; //看到网上有人用这个取中间值，觉得这个很好。 int mid = left + ((right-left)>>1); if(arr[mid] < key) { left = mid + 1; //锁定右半部分 }else if(arr[mid] > key) { right = mid - 1; //锁定左半部分 }else return mid; //返回索引 } return -1; }

递归实现

int binSearchR(int arr[],int low,int high,int key){ if (low<=high) { int mid = (low+high)/2; if(key == arr[mid]) return mid; else if(key<arr[mid]) return binSearch(arr,low,mid-1,key); //左边的递归 else if(key>arr[mid]) return binSearch(arr,mid+1,high,key); //右边的递归 } else return -1; }