Medium — Binary Search | Array | Divide and Conquer

The Problem

Find the index of a target value in a rotated sorted array, where a sorted array has been rotated at some pivot point. Return -1 if the target is not found.

Approach

Use modified binary search by determining which half of the array is properly sorted at each step. Compare the target with the sorted half’s bounds to decide whether to search left or right. This maintains O(log n) complexity despite the rotation.

Time: O(log n) · Space: O(1)

Code

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

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment