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.
*/

class Solution {
public:
    int search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if (not A || n < 0) return -1;
        
        int i = 0, j = n - 1, m = 0;
       
        
        while (i <= j)
        {
            m = i + (j - i) / 2;
            
            if (A[i] == target) return i;
            if (A[j] == target) return j;
            if (A[m] == target) return m;
        
            if (A[i] >= A[m] && A[m] > target)
            {
                j = m - 1;
            }
            else if (A[i] <= A[m] && A[m] < target)
            {
                i = m + 1;
            }
            else
            {
                if (A[i] < target) j = m;
                else if (A[j] > target) i = m;
                else return -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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s