NUHMAN.com

Introduction

LeetCode 33: Search in Rotated Sorted Array asks you to perform a search in a sorted array that has been rotated at some unknown pivot. Despite the rotation, you must solve the problem in O(log n) time.

This is a classic example of applying a modified binary search with conditional logic.

Problem Statement

Given a rotated sorted array of distinct integers and a target value, return the index of the target if it exists in the array. Otherwise, return -1.

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

Examples

go

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

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

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

Approach: Modified Binary Search

Even though the array is rotated, it still has two sorted subarrays. Binary search can still be applied with extra checks to determine which side is sorted.

🔁 Steps:

1. Initialize left = 0, right = len(nums) - 1.
2. While left <= right:

• Find the mid index.
• If nums[mid] == target → return mid.
• Determine if the left half is sorted (nums[left] <= nums[mid]).
• If target is in the left half → shrink right.
• Else → move left.
• Otherwise, the right half is sorted.
• If target is in the right half → move left.
• Else → shrink right.

1. If not found, return -1.

Go Implementation

go

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1

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

        if nums[mid] == target {
            return mid
        }

        // Left half is sorted
        if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            // Right half is sorted
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return -1
}

Example Walkthrough

go

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

1. mid = 3 → nums[3] = 7
2. Left half [4,5,6,7] is sorted, but 0 not in this range
3. Move left to mid+1 → left = 4

Now mid = 5 → nums[5] = 1, target = 0 is less
Right half [1,2] is sorted, move right to mid-1 → right = 4

mid = 4 → nums[4] = 0 ✅ Found!

Time and Space Complexity

MetricComplexityTime ComplexityO(log n)Space ComplexityO(1)

This is achieved through binary search without using any extra space.

Edge Cases

• Empty array → return -1
• Single-element array → return 0 if matched, else -1
• Rotation at index 0 (normal sorted array)

Key Takeaways

• This problem is a great example of how binary search can be adapted for non-trivial structures like rotated arrays.
• Focus on identifying the sorted half of the array and narrowing the search accordingly.