Search in Rotated Sorted Array

• https://leetcode.com/problems/search-in-rotated-sorted-array/

Solution

The key is we can see that one half of the array must be ordered normally (in increasing order). We can therefore look at the normally ordered half to determine whether we should search the left or right half.

Time complexity: O(lgN)

Assume no duplicates

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (target == nums[mid]) {
            return mid;
        }
        // since 'left' could be equal to 'mid', so we have '<=' instead of '<'
        if (nums[left] <= nums[mid]) { // left half is noramlly ordered
            if (target >= nums[left] && target <= nums[mid]) { // target is in the left half
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else { // right half is normally ordered
            if (target >= nums[mid] && target <= nums[right]) { // target is in the right half
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

Recursive approach

public int search(int[] nums, int target) {
    return binarySearch(nums, 0, nums.length-1, target);
}

public int binarySearch(int[] nums, int left, int right, int target){
    if(left>right) 
        return -1;

    int mid = left + (right-left)/2;

    if(target == nums[mid])
        return mid;

    if(nums[left] <= nums[mid]){
        if(nums[left]<=target && target<nums[mid]){
          return binarySearch(nums,left, mid-1, target);
        }else{
          return  binarySearch(nums, mid+1, right, target);
        }
    }else {
        if(nums[mid]<target&& target<=nums[right]){
          return  binarySearch(nums,mid+1, right, target);
        }else{
          return  binarySearch(nums, left, mid-1, target);
        }
    }
}

Follow up: what if duplicates exist

The trick condition is the left and the middle are identical.

For example: In array {2, 2, 3, 4, 2}.

In this case, we can check if the rightmost element is different, if it is, we can search just the right side. Otherwise, we have no other choice but to search for both halves.

public int search(int[] nums, int target) {
    return search(nums, 0, nums.length - 1, target);
}

public int search(int[] nums, int left, int right, int x) {
    if (right < left) return -1;
    int mid = (left + right) / 2;

    if (x == nums[mid]) return mid;

    if (nums[left] < nums[mid]) { // left is normally ordered
        if (x >= nums[left] && x <= nums[mid]) { // the target is on the left 
            return search(nums, left, mid - 1, x); // search left
        } else {
            return search(nums, mid + 1, right, x); // search right
        }
    } else if (nums[mid] < nums[left]) {// right is normally ordered
        if (x >= nums[mid] && x <= nums[right]) { // the target is on the right 
            return search(nums, mid + 1, right, x); // search right
        } else {
            return search(nums, left, mid - 1, x); // search left
        }            
    } else if (nums[left] == nums[mid]) { // left half is ALL repeats
        if (nums[mid] != nums[right]) { // if right is diff, search it
            return search(nums, mid + 1, right, x);
        } else { // else we have to search both halves
            int result = search(nums, left, mid - 1, x); // search left first
            if (result == -1) {
                search(nums, mid + 1, right, x); // search right
            } else {
                return result;
            }
        }
    }
    return -1;
}