33. Search In Rotated Sorted Array

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Modified Binary Search	Use binary search by comparing middle element with the last element to determine which half is sorted. Then check if target lies in the sorted half to decide search direction.	\(O(\log n)\)	\(O(1)\)

Implementation

PythonJavaScriptGo

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)-1

        while l <= r:
            m = (l + r) // 2

            if nums[m] == target:
                return m

            # left sorted side
            if nums[m] >= nums[-1]:
                if nums[0] <= target <= nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            # right sorted side
            else:
                if nums[m] <= target <= nums[-1]:
                    l = m + 1
                else:
                    r = m - 1

        return -1

```