1.我们将一个有序数组(n个元素)从i(号位置)之前放到n位置之后形成的数组为有序循环数组。
2.数组 1 2 4 5 6 7 8
的有序循环数组有
1 2 4 5 6 7 8 （元数组是位置0处的有序循环数组).
2 4 5 6 7 8 1
4 5 6 7 8 1 2
5 6 7 8 1 2 4
6 7 8 1 2 4 5
7 8 1 2 4 5 6
8 1 2 4 5 6 7
3.我们要在有序循环数组中找到一个元素出现的位置(此处假设每个元素出现次数小于等于一)。
a.顺序差 O（n)
b.（二次）二分查找O（2logn) ~ O（logn)。
此处先说明一下二分查找.
若数组有序那么我们取首个位置为l，最后位置为r，中间位置为m=(l+r) /2,要找的元素为val
l<=r时
若A [ m] ==val则找到.
若A[m]>val 则在左边找l=m-1;
若A[m]<val则在右边找r=m+1;
重复过程直到找到.
有下列.
在0 2 3 4 7 8 10 11 70 100 101 中查找 7 ，则会在第三步找到.
若查找5则会在第四步找不到退出。
给出代码:
#include <stdio.h>
#define SIZE 100
int binary_find(int number[],int l,int r,int val){
int lft = l, rit = r ,mid = lft;
while( lft <= rit ){
mid = (rit + lft)/2;
if( number[mid] == val){
return mid;
}else if(number[mid] > val){
rit = mid - 1;
}else{
lft = mid + 1;
}
}
return -1;
}
int main(){
int number[SIZE] = {5,8,10,11};
int i,count=4,val=11,mid=-1;
mid = binary_find(number,0,count-1,,val);
if(mid!=-1){
printf("find :%d at pos:%d!\n",number[mid],mid);
}else{
printf("nomber %d !\n",val);
}
getchar();
return 0;
}
现在来考虑问题在循环有序中的数组中查找元素出现的位置。
假设你知道那个边界点位置为i(i和前面元素有序并且大于每一个i后面的有序序列中的元素元素。
10 11 70 100 101 0 2 3 4 7 8 此处的边界点i为4(从零计算下标)
那么可以将0-4挪到11~15位置,在使用二分查找从(5,15)查找即可。
那么就有新的问题如何找到原序列中的边界点。
1.若果原序列有序，或者只有一个元素直接二分查找。
2.否则为循环多元素的数组，那么需要找分界点.
分界点的特点就在于.
i是分界点下表 a[i] > a[i+1]
若a[pos] < a[r] 则分界点在pos左边（r右边界下标)
若a[pos] > a[l] 则分界点在pos右边（ｌ左边界下标）
相当于换了一次二分查找的条件来查找分界点位置．
找到之后就是来映射分界点左边的元素到分界点右边元素之后。如图
若当前位置为pos，原来右下标为r-1 pos >= r 是真实位置是pos - (r - l - pos);
否则就是本身。
给出代码:
#include <stdio.h>
#define SIZE 100
int main(){
int number[SIZE] = {5,6,7,8};
int i,count=4,val=6;
int lft = 0, rit = count - 1 ,mid = lft,pos = -1,key_pos;
for(i=0;i < count;i++){
printf("%d ",number[i]);
}
if( number[0] <= number[count - 1] ){ //原本为有序串，直接二分查找
while( lft <= rit ){
mid = (rit + lft)/2;
if( number[mid] == val){
printf("find :%d at pos:%d\n",number[mid],mid);
break;
}else if(number[mid] > val){
rit = mid - 1;
}else{
lft = mid + 1;
}
}
if(lft>rit)
printf("no meber :%d\n",val);
}else{ //查找分界点
while( lft <= rit ){
mid = (rit + lft)/2;
if( number[mid] >= number[mid + 1] ){
break;
}else if(number[mid] <= number[count - 1 ]){
rit = mid - 1;
}else{
lft = mid + 1;
}
}
lft = mid + 1,rit = count + mid ,key_pos = mid;
while( lft <= rit ){ //进行查找元素
mid = (rit + lft)/2;
int pos = mid >= count ? mid -(count - key_pos + 1) : mid;
if( number[pos] == val){
printf("find :%d at pos:%d\n",number[pos],pos);
break;
}else if(number[pos] > val){
rit = mid - 1;
}else{
lft = mid + 1;
}
}
if(lft>rit)
printf("no meber :%d\n",val);
}
return 0;
}