Lintcode: 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.

Have you met this question in a real interview? 

Yes

Example

For [4, 5, 1, 2, 3] and target=1, return 2.

For [4, 5, 1, 2, 3] and target=0, return -1.

Challenge

O(logN) time

Tags Expand 

Binary Search Sorted Array Array

In this problem, the key is that we need two equations for binary search condition.
Where the target is located depends not only the A[mid] and target, but also whether this target is located before or after the pivot.
Time: O(logn)
Space: O(1)
In my codes, I use target <>= num[0] to judge the target before or after pivot. In other people's codes, they use target <>=A[left] or A[right]. They are same.
The key is to clarify the logics. I wrote sudo codes before coding:

if target < A[0]
    if A[mid] == target, return mid;
    if A[mid] < target, start = mid + 1;
    if A[mid] > target:
        if A[mid] >= A[0], start = mid + 1;
        if A[mid] < A[0], end = mid - 1;
if target >= A[0]
    if A[mid] == target, return mid;
    if A[mid] < target:
        if A[mid] >= A[0], start = mid + 1;
        if A[mid] < num[0], end = mid - 1;
    if A[mid] > target, end = mid - 1;

class Solution {
    /** 
     * param A : an integer ratated sorted array
     * param target :  an integer to be searched
     * return : an integer
     */
public:
    int search(vector<int> &A, int target) {
        // write your code here
        int start = 0;
        int end = A.size() - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(A[mid] == target) return mid;
            if(target < A[0]){
                if(A[mid] < target) start = mid + 1;
                if(A[mid] > target && A[mid] < A[0]) end = mid - 1;
                if(A[mid] > target && A[mid] >= A[0]) start = mid + 1;
            }
            else{
                if(A[mid] > target) end = mid - 1;
                if(A[mid] < target && A[mid] >= A[0]) start = mid + 1;
                if(A[mid] < target && A[mid] < A[0]) end = mid - 1;
            }
        }
        return -1;
    }
};

Another solution also uses to binary search
one search for pivot, the other search for target
The key is equation from sorted array to rotated array
rotatedIndex = (sortedIndex + pivot) / size    ----pivot the number rotated

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

class Solution { /** * param A : an integer ratated sorted array * param target : an integer to be searched * return : an integer */ //10:47 --12:00 public: int search(vector<int> &A, int target) { // write your code here if(A.size() == 0) return -1; //get pivot -- this way just for no duplicates int start = 0; int end = A.size() - 1; while(start <= end){ int mid = (start + end) / 2; if(A[mid] >= A[0]) start = mid + 1; //Note equation has to be here if use start else if(A[mid] < A[0]) end = mid - 1; } int pivot = start; //get target start = 0; end = A.size() - 1; while(start <= end){ int mid = (start + end) / 2; int middle = (mid + pivot) % A.size(); if(A[middle] < target) start = mid + 1; else end = mid - 1; } int res = start; res = (res + pivot) % A.size(); if(A[res] == target) return res; return -1; } };