把一个有序数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。例如数组{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));
 
}
anyShare分享到:
          
Tagged with:
 

12 Responses to “微软笔试一题:旋转数组元素的查找”

  1. Chris says:

    这道题我也看到了,应该和我的想法是一样的!握手~
    http://www.sunhongfeng.com/2010/10/find_num_in_a_rotate_queue/

  2. Jack says:

    I am glad that I discovered this blog , just the right info that I was searching for! .

  3. danny says:

    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!

  4. bostonmary says:

    Nice post! good information.

  5. I was recommended this website by my cousin. I'm not sure whether this post is written by him as
    no one else know such detailed about my problem. You are wonderful!

    Thanks!

  6. Howdy I am so glad I found your site, Ireally fopund you by mistake,while I was browsing oon Aol ffor something else, Nonetheless I am here now and would just like to say thank you for a fantastic post and a all round interesting blog (I also lovee the
    theme/design), I don't have time to ggo through it all at the moment
    but I have saved it and also included yur RSS feeds, so when I
    have time I will be back too read muc more, Please do
    keep up the superb work.

  7. Johnd976 says:

    certainly like your website however you have to check the spelling on several of your posts. Many of them are rife with spelling problems and I to find it very troublesome to inform the truth nevertheless I will surely come back again. bededafebdeg

  8. Useful info. Fortunate me I discovered your site by accident, and
    I'm stunned why this accident didn't came about in advance!
    I bookmarked it.

  9. Magnificent goods from you, man. I have keep in mind your stuff prior
    to and you are simply too wonderful. I actually like what you've got here,
    really like what you are stating and the way in which wherein you assert it.
    You are making it entertaining and you still take
    care of to keep it wise. I can't wait to learn much more from you.
    This is really a tremendous site.

  10. На нашем сайте Вы можете посмотреть бесплатное порно фото, и эротические фотогалереи божественных малышек на смартфон

  11. На нашем сайте Вы можете загрузить порно фото, и эротические фотопотборки сногшибательных нимф на телефон

  12. This post presents clear idea in support of the new people of blogging, that truly how to
    do blogging and site-building.

Leave a Reply

Note: Commenter is allowed to use '@User+blank' to automatically notify your reply to other commenter. e.g, if ABC is one of commenter of this post, then write '@ABC '(exclude ') will automatically send your comment to ABC. Using '@all ' to notify all previous commenters. Be sure that the value of User should exactly match with commenter's name (case sensitive).