如何快速确定某整数是否在一个被顺序移位的有序整数数组中
RT
[解决办法]
被顺序移位？什么意思？
如果是简单有序二分查找即可
[解决办法]
用折半查找
[解决办法]
是每个数字都以为还是什么？？不明白。
[解决办法]
那得要给出最大值所在位置才能快速查找。
[解决办法]
将数组内容进行移位，使其递增排序，然后使用折半查找。
[解决办法]
确定最小数和最大数的位置,min_pos,max_pos,然后获得长度len
那么mid_pos=(min_pos+max_pos+len)/2,说白了就是二分查找
[解决办法]
先找到最大的位置，当他是个循环队列，然后二分就可以了
[解决办法]
[解决办法]
既然数组是有个有序数组，那么除了数组的首地址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;}