- //============================================================================
- // Function:二元搜索算法,见《Analysis of Algorithms - An Active Learning Approach》
- // W(N)=lg(N+1)/lg(2)
- // A(N)=(k*2^(k+1)-2^k+1)/(2^(k+1)-1),where k=lg(N+1)/lg(2) 假设有N种可能在list中,有N+1中可能不在list中时。
- // In ——待搜索数组 list(类型 int*)。
- // 目标值 target(类型 int);
- // 待搜索数组长度 n(类型 int)
- // Out——无
- // return:目标位置 middle(类型 int,0为起始位置,n为未找到)。
- // note:数组list必须是从小到大排列的有序数组
- // bug:n可以小于list已分配长度,如果n大于list已分配长度,则可能发生内存溢出
- //============================================================================
- int BinarySearch(int *list,int target,int n)
- {
- int middle;
- int start=1;
- int end=n;
- while(start<=end){
- middle=(start+end)/2;
- if(list[middle]==target){
- return middle;
- }
- else if(list[middle]<target){
- start=middle+1;
- }
- else{
- end=middle-1;
- }
- }
- return n;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1707201513154.html
来源: http://www.codesnippet.cn/detail/1707201513154.html