优点:比较次数少，查找速度快，平均性能好；
缺点:要求待查表为有序表，且插入删除困难
int bsearch(int array[], int low, int high, int target) { if (low > high) return -1; int mid = (low + high)/2; if (array[mid]> target) return binarysearch(array, low, mid -1, target); if (array[mid]< target) return binarysearch(array, mid+1, high, target); //if (midValue == target) return mid; }
int bsearchWithoutRecursion(int array[], int low, int high, int target) { while(low <= high) { int mid = (low + high)/2; if (array[mid] > target) high = mid - 1; else if (array[mid] < target) low = mid + 1; else //find the target return mid; } //the array does not contain the target return -1; }
以下程序当key存在时返回它出现的第一个位置，若不存在，返回这样一个下标 i，在此处插入key（原来的a[i],a[i+1],...全部往后移动一个位置）后任然有序。
int lower_bound(int *a, int low, int high, int key) { int index; while (low < high) { index = low + (high - low) / 2; if ( a[index] >= key) high = index; else low = index + 1; } return low; }
原文：http://www.cnblogs.com/ezhengnan/p/3667767.html