Search in Rotated Sorted Array | Leetcode 33 | Optimal Binary Search

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Here’s the [Problem Link] to begin with.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -104 <= target <= 104

Brute Force Solution (Linear Scan)

Intuition & Approach

Check every element until you either hit target or exhaust the array.

Code Implementation

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Scan each index one by one
        for i in range(len(nums)):
            # If the current element matches the target
            if nums[i] == target:
                return i               # return index immediately
        return -1                      # not found

Code Explanation

• Runs through the array sequentially.
• Stops early when target is found.

Dry Run

nums = [4,5,6,7,0,1,2], target = 0
Loop compares in order: 4, 5, 6, 7 → mismatch; index 4 is 0 → return 4.

Time & Space Complexity

• Time: O(n) – one pass over n elements.
• Space: O(1) – constant extra memory.

Conclusion

Works for any array but ignores the sorted-yet-rotated structure, so it’s inefficient for large inputs.

Optimal Solution (Modified Binary Search)

Intuition & Approach

A rotated sorted array still has two sorted halves; at least one half of any sub-array window is ordered.

1. Maintain low, high.
2. Compute mid.
3. If nums[mid] matches target, return mid.
4. Determine which half is sorted:
   • If nums[low] ≤ nums[mid], the left half is sorted.
   • Otherwise, the right half is sorted.
5. Decide which half to discard by seeing where target could lie:
   • If target is within the sorted half’s range, move inside that half; otherwise discard it.
6. Loop until low > high.

Code Implementation

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n         = len(nums)
        low, high = 0, n - 1
        
        while low <= high:
            mid = (low + high) // 2          # middle index
            
            if nums[mid] == target:          # target found
                return mid
            
            # ----- identify the sorted half -----
            if nums[low] <= nums[mid]:       # left half is sorted
                # target lies within the left half?
                if nums[low] <= target <= nums[mid]:
                    high = mid - 1           # search left half
                else:
                    low  = mid + 1           # search right half
            else:                            # right half is sorted
                # target lies within the right half?
                if nums[mid] <= target <= nums[high]:
                    low  = mid + 1           # search right half
                else:
                    high = mid - 1           # search left half
        
        return -1                            # target not found

Code Explanation

• Sorted-half test: nums[low] ≤ nums[mid] implies continuous ordering between low and mid.
• Range check: Compare target with the endpoints of that half to decide where to continue.
• Each iteration halves the remaining search space just like classic binary search.

Dry Run

nums = [4,5,6,7,0,1,2], target = 0

Time & Space Complexity

• Time: O(log n) – halving the window each step.
• Space: O(1) – only pointers and indices.

Conclusion

By detecting which side of the pivot is still sorted and discarding the other half, this modified binary search finds target in logarithmic time, fully using the array’s structure for optimal performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.