今天在读Jon Bentley的Programming Pearls，看到二分查找处，据说Jon当年做了测验90%的学生都给写错了，
我就顺手也写了个试试，Jon的学生都是世界Top系列名校的学生，所以我怀疑我的程序中也存在我没测试出来的缺陷
把程序贴出来，欢迎大家提bug，讨论。
#include <stdio.h> int binarySearch(int a[],int size,int target) { int lo=0,hi=size-1; int middle; if(a[lo]==target) return lo; if(a[hi]==target) return hi; for(;lo<hi;) { middle=(lo+hi)/2; if(a[middle]<target) { if(middle==lo) return -1; lo=middle; continue; } else if(a[middle]>target) { if(middle==hi) return -1; hi=middle; continue; } else return middle; } return -1; } int main(void) { int a[10]={1,3,5,7,9,11,14,16,17,18}; int i; for(i=0;i<10;++i) printf("%d/t",a[i]); printf("/n"); printf("index of 0 is %d /n",binarySearch(a,10,0)); printf("index of 1 is %d /n",binarySearch(a,10,1)); printf("index of 11 is %d /n",binarySearch(a,10,11)); printf("index of 13 is %d /n",binarySearch(a,10,13)); printf("index of 14 is %d /n",binarySearch(a,10,14)); printf("index of 18 is %d /n",binarySearch(a,10,18)); printf("index of 20 is %d /n",binarySearch(a,10,20)); return 0; }
运行结果如下：其中-1代表没有找到该元素，否则返回数组下标（下标从0开始计）；
[jim@ts850 algoriths]$ gcc -o binarySearch binarySearch.c [jim@ts850 algoriths]$ ./binarySearch 1 3 5 7 9 11 14 16 17 18index of 0 is -1 index of 1 is 0 index of 11 is 5 index of 13 is -1 index of 14 is 6 index of 18 is 9 index of 20 is -1 [jim@ts850 algoriths]$
2011-04-15
