Solving Search in Rotated Array in Go: Step-by-Step Guide

Introduction to Search in Rotated Sorted Array

The "Search in Rotated Sorted Array" problem is a classic algorithmic challenge that frequently appears in coding interviews and real-world applications. A rotated sorted array is an array that was originally sorted in ascending order but has been rotated at some pivot point. For example, [0, 1, 2, 3, 4, 5, 6, 7] rotated at pivot index 3 becomes [4, 5, 6, 7, 0, 1, 2, 3].

The goal is to find the index of a target value in this rotated array efficiently. While a linear scan would solve this in O(n) time, the optimal solution leverages a modified binary search to achieve O(log n) time complexity. This tutorial walks through the problem in Go, explaining the logic, implementation, and best practices.

Why This Problem Matters

Understanding how to search a rotated sorted array sharpens your ability to reason about binary search variants. Binary search is one of the most powerful algorithmic tools, but its variations require careful handling of boundary conditions. Mastering this problem teaches you how to:

Identify which half of a divided array is properly sorted
Decide which half to discard based on the target's position
Handle edge cases such as duplicates, missing targets, and single-element arrays

In practice, rotated arrays appear in scenarios like circular buffers, log files that wrap around, and load-balanced ring data structures. Efficient searching in these structures is essential for performance-critical systems.

Understanding the Problem

Given an array nums that is sorted in ascending order and rotated at an unknown pivot, and a target value target, return the index of target if it exists in the array, or -1 if it does not. The algorithm must run in O(log n) time.

For example:

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

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

The Core Insight: Modified Binary Search

The key observation is that when you split a rotated sorted array at any midpoint, at least one of the two halves will always be sorted. You can determine which half is sorted by comparing the middle element with the leftmost element:

If nums[mid] >= nums[left], the left half is sorted.
Otherwise, the right half is sorted.

Once you know which half is sorted, you can check whether the target lies within that sorted half's range. If it does, search that half; otherwise, search the other half. This decision process allows you to discard half of the remaining elements at each step, preserving the logarithmic complexity of binary search.

Step-by-Step Implementation in Go

Let's build the solution incrementally. First, we set up the standard binary search loop with two pointers, left and right.

package main

import "fmt"

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
        }

        // Determine which half is sorted
        if nums[left] <= nums[mid] {
            // Left half is sorted
            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
}

func main() {
    nums := []int{4, 5, 6, 7, 0, 1, 2}
    fmt.Println(search(nums, 0)) // Output: 4
    fmt.Println(search(nums, 3)) // Output: -1
}

Breaking Down the Code

The loop continues while left <= right, ensuring we check single-element ranges. We compute mid using left + (right-left)/2 instead of (left+right)/2 to avoid integer overflow, a best practice in languages where overflow is possible.

When nums[mid] equals the target, we return mid immediately. Otherwise, we determine which half is sorted. The condition nums[left] <= nums[mid] uses <= rather than < to handle the case where left and mid point to the same element, which happens when the search range has only one or two elements.

If the left half is sorted, we check whether the target falls within [nums[left], nums[mid]). If so, we narrow the search to the left half; otherwise, we search the right half. The same logic applies symmetrically when the right half is sorted.

Handling Edge Cases

Several edge cases deserve attention when implementing this algorithm:

Empty array: The loop never executes, and the function returns -1 immediately.
Single element: The loop runs once, comparing the only element to the target.
Non-rotated array: The algorithm still works because the left half is always sorted, and the logic reduces to standard binary search.
Target not present: The loop exits when left > right, returning -1.

Let's verify these cases with a test function:

func testEdgeCases() {
    cases := []struct {
        nums   []int
        target int
        want   int
    }{
        {[]int{}, 5, -1},
        {[]int{1}, 1, 0},
        {[]int{1}, 0, -1},
        {[]int{1, 2, 3, 4, 5}, 3, 2},
        {[]int{5, 1, 2, 3, 4}, 5, 0},
        {[]int{3, 4, 5, 1, 2}, 2, 4},
        {[]int{2, 3, 4, 5, 1}, 1, 4},
    }

    for _, c := range cases {
        got := search(c.nums, c.target)
        status := "PASS"
        if got != c.want {
            status = "FAIL"
        }
        fmt.Printf("%s: nums=%v target=%d got=%d want=%d\n",
            status, c.nums, c.target, got, c.want)
    }
}

Variant: Searching with Duplicates

A harder variant allows duplicate values in the array, for example [2, 5, 6, 0, 0, 1, 2]. The challenge is that when nums[left] == nums[mid] == nums[right], you cannot determine which half is sorted. The solution is to shrink the search range by incrementing left and decrementing right until the ambiguity resolves. This degrades worst-case time to O(n) but remains efficient on average.

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

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

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

        // Handle ambiguity when left, mid, and right are equal
        if nums[left] == nums[mid] && nums[mid] == nums[right] {
            left++
            right--
        } else if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return false
}

Notice that this variant returns a boolean rather than an index, because duplicates make the index ambiguous and the problem typically asks only whether the target exists.

Best Practices

When implementing search in a rotated sorted array, keep these best practices in mind:

Use overflow-safe midpoint calculation: Always compute mid as left + (right-left)/2 rather than (left+right)/2. While Go's int is platform-dependent and unlikely to overflow on 64-bit systems, this habit prevents bugs in other languages and on constrained platforms.
Prefer inclusive bounds: Using left <= right with right = len(nums)-1 is a common and intuitive convention. Stick with one convention across your codebase to avoid off-by-one errors.
Test with small arrays: Arrays of length 0, 1, and 2 are where most bugs hide. Always include these in your test suite.
Document assumptions: Clearly state whether your function handles duplicates and what it returns when the target is missing. This prevents misuse by other developers.
Consider readability over micro-optimization: The O(log n) complexity is already excellent. Avoid clever tricks that obscure the logic unless profiling shows a real performance need.

Performance Analysis

The standard algorithm without duplicates runs in O(log n) time because each iteration discards half of the remaining elements. Space complexity is O(1) since we only use a few integer variables. The duplicate-handling variant has a worst-case time of O(n) when all elements are identical and the target is absent, but it remains O(log n) on average for typical inputs.

For comparison, a naive linear scan would always take O(n) time. On an array of one million elements, binary search performs roughly 20 comparisons, while linear search averages 500,000. This difference is significant in performance-sensitive applications.

Conclusion

Searching a rotated sorted array is a deceptively simple problem that tests your understanding of binary search and boundary conditions. By identifying which half of the array is sorted at each step and using that knowledge to discard the irrelevant half, you achieve efficient O(log n) lookup. The Go implementation is concise, but the logic requires careful attention to inclusive bounds, overflow-safe midpoint calculation, and edge cases like empty or single-element arrays. With the foundation covered here, including the duplicate-handling variant, you are well-equipped to tackle this problem in interviews and apply the same reasoning to other binary search derivatives in real-world Go programs.