怎么快速确定某整数是否在一个被顺序移位的有序整数数组中
如何快速确定某整数是否在一个被顺序移位的有序整数数组中RT[解决办法]被顺序移位？什么意思？如果是简单有
如何快速确定某整数是否在一个被顺序移位的有序整数数组中[解决办法] [解决办法] [解决办法] [解决办法] [解决办法] [解决办法] [解决办法] [解决办法]
探讨 [解决办法] 既然数组是有个有序数组，那么除了数组的首地址p和长度len外，还需要一个参数指定最小整数的位置pos，则数组可分为2子数组，第一个子数组是a[0]..a[pos-1], 第二个子数组a[pos]..a[len-1]。分别在2个子数组中做2分查找即可。
如果不知道最小元素的位置，先做个顺序查找，可找到最小元素的位置，时间复杂度为O(len),二分查找的时间复杂度为O(log2(len))
[解决办法] 用改进的折半查找吧，大概写了一个
if(elem>=a[0])
{
int left=0,right=size-1;
int mid=left+(right-left)/2;
while(left<right)
{
mid=left+(right-left)/2;
if(a[mid]==elem)
{
return mid;
}
else
{
if(a[mid]<elem)
{
if(a[mid]<a[left])
{
right=mid-1;
}
else
{
left=mid+1;
}
}
else
{
right=mid-1;
}
}
}
return -1;
}
else
{
int left=0,right=size-1;
int mid=left+(right-left)/2;
while(left<right)
{
mid=left+(right-left)/2;
if(a[mid]==elem)
{
return mid;
}
else
{
if(elem<a[mid])
{
if(a[mid]<a[right])
{
right=mid-1;
}
else
{
left=mid+1;
}
}
else
{
left=mid+1;
}
}
}
return -1;
}
[解决办法] 探讨 [解决办法] 探讨 [解决办法] 抱歉，这样的解法只能用在特殊场合，不具普适性。
比如你说这个问题，就是因为只有一个出线单数次。xor运算的特点就是同一数值经过双数次运算后结果会为零，最终只有那个单数次出现的家伙被保留下来。如果出现单数次的不止一个，则该算法无用。
你在顶楼所提状况就没有这样的特殊规律可供使用了。如果一定要说有，那就是原本是个有序数组，经循环移位后仍旧保持局部有序的特性。不过这个特性已经被折半查找利用过了，否则就只能靠遍历寻找了。
[解决办法] 首先用二分法查找“分界点”，然后对分成的两部分，分别用二分法查找。
总共是O(log(n))复杂度。
C/C++ code// 数组x是有序数组循环移位，数组长度len必需大于1// 找到一个位置pos，这个位置的数大于等于x[0]，这个数下一个小于等于x[len-1]// 结果：[0,pos]之间的数是有序的，[pos,len-1]之间的数是有序的int max_pos( int *x, int len ) { int beg = 0, end = len - 1; int left = x[0], right = x[len-1]; while( beg <= end ) { int mid = ( beg + end ) / 2; if( x[mid] < left ) end = mid - 1; else if( x[mid+1] > right ) beg = mid + 1; else return mid; } return -1;}
