把一个有序数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转。
现在给出旋转后的数组和一个数，旋转了多少位不知道，要求给出一个算法，算出给出的数在该数组中的下标，如果没有找到这个数，则返回-1。要求查找次数不能超过n。
这个题要想尽量减少是件复杂度，我觉得使用二分查找最好，只是需要稍微变化下，时间复杂度仍然是O(logn)，下面给出C语言描述的程序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | #include <stdio.h> int find(int* array, int n, int a){ int val; if(n==1){ if(array[0]==a) return 0; else return -1; } if(array[n/2-1]>array[0]){ if(a>array[n/2-1] || a<array[0]){ if((val=find(array+n/2, n-n/2, a))!=-1){ return val+n/2; } else return -1; } else if((val=find(array, n/2,a))!=-1){ return val; } return -1; } else{ if(array[n-1]<a || array[n/2]>a){ if((val=find(array, n/2, a))!=-1){ return val; } } else if((val=find(array+n/2, n-n/2,a))!=-1){ return val+n/2; } } return -1; } int main(){ int n; scanf("%d", &n); //n是数组长度 int array[100]; int i, j , k; for(i=0;i<n;i++){ scanf("%d",&array[i]);//输入数组元素 } int a; scanf("%d", &a); //输入要查找元素 printf("%d\n",find(array, n, a)); } |
这道题我也看到了，应该和我的想法是一样的！握手~
http://www.sunhongfeng.com/2010/10/find_num_in_a_rotate_queue/
I am glad that I discovered this blog , just the right info that I was searching for! .
Wow, amazing blog format! How lengthy have you ever been running a blog for? you made blogging look easy. The total glance of your web site is great, let alone the content material!
Nice post! good information.