C++实现旋转数组的二分查找

2024-04-08 06:36:04 507

#include<iostream> usingnamespacestd; intsequentialSearch(int*array,intsize,intdestValue) { intpos=-1; if(array==NULL||size<=0) returnpos; for(inti=0;i<size;i++) { if(array[i]==destValue) { pos=i; break; } } returnpos; } intnormalBinarySearch(int*array,intleftPos,intrightPos,intdestValue) { intdestPos=-1; if(array==NULL||leftPos<0||rightPos<0) { returndestPos; } intleft=leftPos; intright=rightPos; while(left<=right) { intmid=(right-left)/2+left; if(array[mid]==destValue) { destPos=mid; break; } else if(array[mid]<destValue) { left=mid+1; } else { right=mid-1; } } returndestPos; } introtateBinarySearch(int*array,intsize,intdestValue) { intdestPos=-1; if(array==NULL||size<=0) { returndestPos; } intleftPos=0; intrightPos=size-1; while(leftPos<=rightPos) { if(array[leftPos]<array[rightPos]) { destPos=normalBinarySearch(array,leftPos,rightPos,destValue); break; } intmidPos=(rightPos-leftPos)/2+leftPos; if(array[leftPos]==array[midPos]&&array[midPos]==array[rightPos]) { destPos=sequentialSearch(array,size,destValue); break; } if(array[midPos]==destValue) { destPos=midPos; break; } if(array[midPos]>=array[leftPos]) { if(destValue>=array[leftPos]) { destPos=normalBinarySearch(array,leftPos,midPos-1,destValue); break; } else { leftPos=midPos+1; } } else { if(array[midPos]<=array[rightPos]) { destPos=normalBinarySearch(array,midPos+1,rightPos,destValue); break; } else { rightPos=midPos-1; } } } returndestPos; } intmain() { //intarray[]={3,4,5,1,2}; //intarray[]={1,2,3,4,5}; //intarray[]={1,0,1,1,1}; //intarray[]={1,1,1,0,1}; //intarray[]={1}; //intarray[]={1,2}; intarray[]={2,1}; constintsize=sizeofarray/sizeof*array; for(inti=0;i<=size;i++) { intpos=rotateBinarySearch(array,size,array[i]); cout<<"find"<<array[i]<<"at:"<<pos+1<<endl; } for(inti=size;i>=0;i--) { intpos=rotateBinarySearch(array,size,array[i]); cout<<"find"<<array[i]<<"at:"<<pos+1<<endl; } }

C++实现旋转数组的二分查找

热门推荐

随机推荐