C++实现旋转数组的二分查找
本文实例讲述了C++实现旋转数组的二分查找方法，分享给大家供大家参考。具体方法如下：
题目要求：
旋转数组，如{3,4,5,1,2}是{1,2,3,4,5}的一个旋转，要求利用二分查找查找里面的数。
这是一道很有意思的题目，容易考虑不周全。这里给出如下解决方法：
#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++算法设计的学习有所帮助。