Find element in rotated array

Image a sorted array 1,2,3,8,10,20,49. After a shift happens, for example, it happens at 10. Suppose all elements including and after 10 are pasted in the beginning. The array becomes 10,20,49,1,2,3,8. Now ask to find an element (say, 3). What is your best solution?

C++:
01 int findMax(int *A, int size)
02 {
03     int a=A[0];
04     int left=0;
05     int right=size1;
06     while(left<=right){
07         int mid=(left+right)/2;
08         if(A[mid]>A[(mid+1)%size])
09             return mid;
10         if(A[mid]>a)
11             left=mid+1;
12         else
13             right=mid1;
14     }
15     return 1;
16 }
17 int BinarySearch(int* A, int start, int end, int size, int a)
18 {
19     if((start>end)||(end>size1))
20         return 1;
21     while(start<=end){
22         int mid=(start+end)/2;
23         if(A[mid]==a)
24             return mid;
25         if(A[mid]<a)
26             start=mid+1;
27         else
28             end=mid1;
29     }
30     return 1;
31 }
32 
33 int findElement(int* A, int size, int peak, int a)
34 {
35     if(A[0]==a)
36         return 0;
37     if(A[0]<a)
38         return BinarySearch(A, 0, peak, size,a);
39     if(A[0]>a)
40         return BinarySearch(A, peak+1,size1,size,a);
41 
42 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s