Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

C++:
01 class Solution {
02 public:
03     int search(int A[], int n, int target) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int p=0;
07         int q=n1;
08         while(p<=q)
09         {
10             int t=p+(qp)/2;
11             if(A[t]==target)
12                 return t;
13             if(A[p]==target)
14                 return p;
15             if(A[q]==target)
16                 return q;
17             if(A[p]<A[t])
18             {
19                if((target>A[p])&&(target<A[t]))
20                    q=t1;
21                else
22                    p=t+1;
23             }
24             else
25             {
26                 if((target>A[t])&&(target<A[q]))
27                     p=t+1;
28                 else
29                     q=t1;
30             }
31         }
32         return 1;
33     }
34 };
Advertisements
This entry was posted in Array and linked list, Binary search. 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