33. Search in Rotated Sorted Array

# Medium

Solution

Case 1: no rotated, just do binary search as regular

Case 2: is rotated, find the pivot, and do binary search in one of two parts

Consider edge case: 0 element

How to find the pivot?

if nums[mid] < left:
    left = left
    right = mid
else:
    left = mid
    right = right

Better solution:

1. find the smallest element in the array which is the pivot.

2. only search left or right part of this array by Binary Search

Python

// Some code
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # find the pivot, which is smallest element in the list
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
                
        pivot = left
        left = 0
        right = len(nums) - 1
        # [1, 3], target = 3, then the pivot is 0 but not 2, so search consider right part first
        if target >= nums[pivot] and target <= nums[right]:
            left = pivot
        else:
            right  = pivot
            
        # binary search
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
                
        return -1

Java I

// Some code
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            if(nums[mid] > nums[right])
                left = mid + 1;
            else
                right = mid;
        }
        System.out.print(left);
        int pivot = left;
        left = 0;
        right = nums.length - 1;
        
        if(target >= nums[pivot] & target <= nums[right])
            left = pivot;
        else
            right = pivot;
        
        return search(nums, target, left, right);
    }
    
    public int search(int[] nums, int target, int left, int right) {
        // edge case
        if(left > right)
            return -1;
        
        // regular case
        int mid = left + (right - left)/2;
        if(nums[mid] == target)
            return mid;
        else if(nums[mid] > target)
            return search(nums, target, left, mid - 1);
        else
            return search(nums, target, mid + 1, right);
    }
}

Java II (more efficient)

// Some code
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left)/2;
            if(nums[mid] == target)
                return mid;
            // [start, mid] not rotated
            // [3, 1] is rotated, but only put here make sense
            else if(nums[mid] >= nums[left]) {
                if(target >= nums[left] && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            // [start, mid] is rotated
            else {
                if(target > nums[mid] && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }
}