(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.

Thoughts:
This is a modified version of binary search. Each time we half the array, and determine which part is sorted (there must be at least one of them). We then check if the target falls in the sorted part, we then apply the original version of binary search to it. Otherwise we recursively or iteratively go to the other half.

Code (Java):

public class Solution {
    public int search(int[] A, int target) {
        int low = 0;
        int high = A.length - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(target == A[mid])
                return mid;
            if(A[low] <= A[mid]) { // left part sorted
                if(A[low] <= target && target < A[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else { // right part sorted
                if(A[mid] < target && target <= A[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return -1;
    }
}

Code (C++):

class Solution {
public:
    int search(int A[], int n, int target) {
        int low = 0;
        int high = n - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(A[mid] == target)
                return mid;
            if(A[low] <= A[mid]) { // left part sorted
                if(A[low] <= target && target < A[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else {
                if(A[mid] < target && target <= A[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return -1;
    }
};
Advertisements

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

%d bloggers like this: