（一）二分的模版：
int binary_search(int *array, int length, int key) {
int start = 0, end = length - 1;
while(end >= start) {
int middle = start + (end - start) / 2;
int tmp = array[middle];
if(tmp < key) start = middle + 1;
else if (tmp > key) end = middle - 1;
else return middle;
}
return -1;
}
（二）
#include
#include
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; int bsearch(int* A, int x, int y, int v) { int m; while(x < y) { m = x+(y-x)/2; if(A[m] == v) return m; else if(A[m] > v) y = m; else x = m+1; } return -1; } int main() { int i; for(i = 1; i <= 11; i++) assert(bsearch(A, 0, 11, i) == i-1); printf("Ok!\n"); return 0; }
（三）利用二分法找上下界
#include
#include
#include
using namespace std; int A[] = {1, 2, 3, 3, 3, 3, 3, 5, 6}; int lower_bound(int *array, int length, int v) { int start = 0, end = length - 1; while(start <= end) { int middle = start + (end - start) / 2; int tmp = array[middle]; if(array[middle] >= v) end = middle - 1; else start = middle + 1; } return start; } int upper_bound(int *array, int length, int v) { int start = 0, end = length-1; while(start <= end) { int middle = start + (end - start) / 2; int tmp = array[middle]; if(array[middle] <= v) start = middle + 1; else end = middle - 1; } return start; } int main() { cout << lower_bound(A, 9, 3) << endl << upper_bound(A, 9, 3) << endl; return 0; }