//============================================================================ // Name : 编程之美程序改错.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> #include<stdlib.h> using namespace std; int findValue(int *a,int begin,int end,int v) { int mid; while(begin<=end) { mid=begin+(end-begin)/2; if(a[mid]==v) return mid; if(a[mid]>v) { end=mid-1; } else begin=mid+1; } return -1; } int findMinValue(int *a,int begin,int end,int v) { int mid; int begin1=begin; while(begin<=end) { mid=begin+(end-begin)/2; if(a[mid]==v) break; if(a[mid]>v) { end=mid-1; } else begin=mid+1; } if(begin>end) return -1; if(mid-1>=begin1&&a[mid-1]==v) mid--; return mid; } int findMaxValue(int *a,int begin,int end,int v) { int mid; int length=end; while(begin<=end) { mid=begin+(end-begin)/2; if(a[mid]==v) break; if(a[mid]>v) { end=mid-1; } else begin=mid+1; } if(begin>end) return -1; if(mid+1<=length&&a[mid+1]==v) mid++; return mid; } int findMaxiValue(int *a,int begin,int end,int v) { int mid; if(a[end]<v) return end; if(a[begin]>=v) return -1; while(end-begin>1) { mid=begin+(end-begin)/2; if(a[mid]>v) { end=mid; } else if(a[mid]<v) begin=mid; else if(a[mid]==v) break; } if(end-begin>1) { if(mid-1>0&&a[mid-1]==v) mid--; mid--; return mid; } return begin; } int findMiniValue(int *a,int begin,int end,int v) { int mid; if(a[end]<=v) return -1; if(a[begin]>v) return begin; while(end-begin>1) { mid=begin+(end-begin)/2; if(a[mid]>v) { end=mid; } else if(a[mid]<v) begin=mid; else if(a[mid]==v) break; } if(end-begin>1) { if(mid+1>0&&a[mid+1]==v) mid++; mid++; return mid; } return end; } int brsearch(char **arr,int begin,int end,char *v) { int mid; while(begin<=end) { mid=begin+(end-begin)/2; if(strcmp(arr[mid],v)>0) { end=mid-1; } else if(strcmp(arr[mid],v)<0) { begin=mid+1; } else if(!strcmp(arr[mid],v)) { break; } } if(begin>end) throw new string("no v"); cout<<"mid is"<<mid<<endl; while(mid+1<=end&&!strcmp(arr[mid+1],v)) mid++; return mid; } int main() { char **a=new char*[10]; a[0]=new char[10]; a[0]="hello"; a[1]=new char[10]; a[1]="yello"; a[2]=new char[10]; a[2]="yello"; a[3]=new char[10]; a[3]="zebra"; char v[10]="zebra"; cout<< brsearch(a,0,3,v)<<endl; int a1[20]={1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,11,11}; cout<<findValue(a1,0,18,11)<<endl; cout<<findMinValue(a1,0,18,9)<<endl; cout<<findMaxValue(a1,0,18,19)<<endl; cout<<findMaxiValue(a1,0,18,10)<<endl; cout<<findMiniValue(a1,0,18,8)<<endl; return 0; }
