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 int search(int A[], int n, int target) {
02     int i=0;
03     int j=n1;
04     while(i<=j){
05         int mid=(i+j)/2;
06         if(A[mid]==target)
07             return mid;
08         if(A[i]<A[mid]){
09             if((A[i]<=target)&&(target<A[mid]))
10                 j=mid1;
11             else
12                 i=mid+1;
13         }
14         else if(A[i]>A[mid]){
15             if((A[mid]<target)&&(target<=A[j]))
16                 i=mid+1;
17             else
18                 j=mid1;
19         }
20         else
21             i++;
22     }
23     return 1;
24 }
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