033.SearchInRotatedSortedArray.md

tags: Array, BinarySearch

#LeetCode 33 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.

Difficulty Hard

Related Problems
[LeetCode 153] Find Minimum in Rotated Sorted Array I
[LeetCode 154] Find Minimum in Rotated Sorted Array II

Analysis

This problem is a variation of binary search. The key point is to find in which part the target are in.

situation 1:

6 7 0 1 2 4 5    0 is in left part
      ^
     mid

situation 2:

2 4 5 6 7 0 1    0 is in right part
      ^
     mid     

Note: In any case, there always has a part is sorted.

To be specific:

• when A[0] <= A[mid], the left part is sorted!
• when A[mid] <= A[n - 1] (or A[0] > A[mid]), the right part is sorted!

Solutions

1. Cpp solution 6ms

class Solution {
public:
    int search(vector<int> &nums, int target) {
        int low = 0, high = nums.size() - 1;
        while (low <= high) {
            const int mid = low + (high - low) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[low] <= nums[mid]) {
                if (nums[low] <= target && target < nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return -1;
    }
};

2. Cpp solution

Recursion binary search

class Solution {
public:
    int search(int nums[], int n, int target) {
        return searchRotatedSortedArray(nums, 0, n-1, target);
    }
    
    int searchRotatedSortedArray(int nums[], int low, int high, int target) {
        if(low > high) return -1;
        int mid = low + (high - low)/2;
        if(nums[mid] == target) return mid;
        if(nums[mid] < nums[high]) { // right half sorted
            if(target > nums[mid] && target <= nums[high])
                return searchRotatedSortedArray(nums, mid + 1, high, target);
            else
                return searchRotatedSortedArray(nums, low, mid - 1, target);
        }
        else {  // left half sorted
            if(target >= nums[low] && target < nums[mid]) 
                return searchRotatedSortedArray(nums, low, mid - 1, target);
            else
                return searchRotatedSortedArray(nums, mid+1, high, target);
        }
    }
};

3. Go solution 6ms

func search(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if nums[mid] == target {
            return mid
        }
        if nums[lo] <= nums[mid] {
            if nums[lo] <= target && target < nums[mid] {
                hi = mid - 1
            } else {
                lo = mid + 1
            }
        } else {
            if nums[mid] < target && target <= nums[hi] {
                lo = mid + 1
            } else {
                hi = mid - 1
            }
        }
    }

    return -1
}

Reference