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

Understand the problem:
The problem gives a sorted array which is rotated at some pivot, search for a target value. This problem clearly indicates that we do find the number in O(logn) time, just as binary search. 

One naive idea is to find the pivot and rotate the array back, then we can apply the binary search. But rotating the array would take on average O(n) time, which is not allowed in this problem. 

Solution:
The solution is very similar to binary search. Note that no matter how we rotated the array, there must be at least one part which is sorted. If the target is at the sorted part, we just search that part until we found; else we go the unsorted part. 

Code (Java):

public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (A[mid] == target) {
                return mid;
            }
            
            if (A[lo] <= A[mid]) {
                if (target >= A[lo] && target < A[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (A[mid] < target && target <= A[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}

Discussion:
Now let's analyze the complexity. If the target just falls into the sorted part, the complexity could be O(logn). How about the worst case, where target is always not in the sorted part, then we have to iterate all the data of the array, then the complexity becomes O(n). So on average, we can see that the complexity is O(logn).

Summary:
This is an extension of the binary search. So it is very important that you got familiar with the binary search. 

Update on 9/29/14:

public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (A[mid] == target) {
                return mid;
            }
            
            if (A[lo] <= A[mid]) {
                if (A[lo] <= target && target < A[mid]) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            } else {
                if (A[mid] < target && target <= A[hi] ) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
        }
        
        if (target == A[lo]) {
            return lo;
        }
        
        if (target == A[hi]) {
            return hi;
        }
        
        return -1;
        
    }
}

Update on 7/13/18:

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int ans = -1;
        
        int lo = 0;
        int hi = nums.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            } else {
                // case 1: left half is sorted
                //
                if (nums[lo] < nums[mid]) {
                    if (target >= nums[lo] && target < nums[mid]) {
                        hi = mid - 1;
                    } else {
                        lo = mid + 1;
                    }
                } else if (nums[mid] < nums[hi]) {
                    if (target > nums[mid] && target <= nums[hi]) {
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
            }
        }
        
        if (nums[lo] == target) {
            return lo;
        }
        
        if (nums[hi] == target) {
            return hi;
        }
        
        return -1;
    }
}