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

Java II (more efficient)