Solving Find Minimum in Rotated Sorted Array in Go: Step-by-Step Guide

Introduction to the Problem

The "Find Minimum in Rotated Sorted Array" problem is a classic algorithmic challenge frequently encountered in coding interviews and competitive programming. Given an array of unique integers that was originally sorted in ascending order and then rotated at some unknown pivot, your task is to find the smallest element in the array efficiently.

For example, the array [3, 4, 5, 1, 2] is a rotation of [1, 2, 3, 4, 5] rotated three times. The minimum element here is 1. While a linear scan would solve this in O(n) time, the real challenge is achieving O(log n) time complexity using a modified binary search.

Why This Problem Matters

This problem is more than just an interview exercise. It teaches fundamental concepts that apply to real-world scenarios:

Binary search mastery: It forces you to think beyond standard binary search and adapt the algorithm to non-trivial conditions.
Real-world applications: Rotated sorted arrays appear in systems like circular buffers, log rotation systems, and load-balanced server queues where you need to find the "starting point" efficiently.
Problem decomposition: It trains you to identify which half of a data structure contains the answer based on partial ordering information.
Foundation for variants: Understanding this problem prepares you for related challenges like "Search in Rotated Sorted Array" and handling duplicates.

Understanding the Rotated Array Structure

Before diving into code, it's crucial to understand the structure of a rotated sorted array. When a sorted array is rotated, it creates two sorted subarrays. The minimum element sits at the boundary where these two subarrays meet — it's the only element that is smaller than its previous element.

Consider these examples:

[4, 5, 6, 7, 0, 1, 2] — minimum is 0 at index 4
[11, 13, 15, 17] — not rotated, minimum is 11 at index 0
[2, 1] — minimum is 1 at index 1

The key insight is that by comparing the middle element with the rightmost element, you can determine which half contains the minimum. If the middle element is greater than the rightmost element, the minimum must be in the right half. Otherwise, it's in the left half (including the middle element itself).

Step-by-Step Algorithm Explanation

The Binary Search Approach

The algorithm works as follows:

Initialize two pointers, left at the start and right at the end of the array.
While left is less than right, calculate the middle index.
Compare the middle element with the rightmost element.
If nums[mid] > nums[right], the minimum is in the right half, so set left = mid + 1.
Otherwise, the minimum is in the left half (including mid), so set right = mid.
When the loop ends, left and right converge to the minimum element's index.

The reason we compare with the rightmost element rather than the leftmost is that comparing with the left doesn't always give clear direction. For instance, if nums[mid] > nums[left], the left half could be sorted, but the minimum could still be in either half depending on whether a rotation occurred in the right half.

Walkthrough Example

Let's trace through [4, 5, 6, 7, 0, 1, 2]:

Iteration 1: left=0, right=6, mid=3. nums[3]=7 > nums[6]=2, so left=4.
Iteration 2: left=4, right=6, mid=5. nums[5]=1 <= nums[6]=2, so right=5.
Iteration 3: left=4, right=5, mid=4. nums[4]=0 <= nums[5]=1, so right=4.
Loop ends: left=right=4, minimum is nums[4]=0.

Complete Go Implementation

Here is the complete, production-ready Go implementation of the solution:

package main

import "fmt"

// findMin finds the minimum element in a rotated sorted array
// with unique elements in O(log n) time.
func findMin(nums []int) int {
    if len(nums) == 0 {
        panic("array must not be empty")
    }

    left, right := 0, len(nums)-1

    // If the array is not rotated (or has one element),
    // the first element is the minimum.
    if nums[left] <= nums[right] {
        return nums[left]
    }

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

        if nums[mid] > nums[right] {
            // The minimum is in the right half
            left = mid + 1
        } else {
            // The minimum is in the left half (including mid)
            right = mid
        }
    }

    // left and right have converged to the minimum index
    return nums[left]
}

func main() {
    testCases := [][]int{
        {3, 4, 5, 1, 2},
        {4, 5, 6, 7, 0, 1, 2},
        {11, 13, 15, 17},
        {2, 1},
        {1},
        {2, 3, 4, 5, 1},
    }

    for _, tc := range testCases {
        fmt.Printf("Array: %v -> Minimum: %d\n", tc, findMin(tc))
    }
}

When you run this program, the output will be:

Array: [3 4 5 1 2] -> Minimum: 1
Array: [4 5 6 7 0 1 2] -> Minimum: 0
Array: [11 13 15 17] -> Minimum: 11
Array: [2 1] -> Minimum: 1
Array: [1] -> Minimum: 1
Array: [2 3 4 5 1] -> Minimum: 1

Handling Duplicates Variant

A common follow-up question involves arrays that may contain duplicates. When duplicates are present, the standard approach can fail because nums[mid] might equal nums[right], making it impossible to determine which half contains the minimum. In this case, you safely decrement right by one.

package main

import "fmt"

// findMinWithDuplicates handles rotated sorted arrays that may
// contain duplicate values. Worst-case time becomes O(n).
func findMinWithDuplicates(nums []int) int {
    if len(nums) == 0 {
        panic("array must not be empty")
    }

    left, right := 0, len(nums)-1

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

        if nums[mid] > nums[right] {
            // Minimum is in the right half
            left = mid + 1
        } else if nums[mid] < nums[right] {
            // Minimum is in the left half (including mid)
            right = mid
        } else {
            // nums[mid] == nums[right]: cannot decide, shrink right
            right--
        }
    }

    return nums[left]
}

func main() {
    testCases := [][]int{
        {2, 2, 2, 0, 1},
        {1, 3, 3},
        {3, 3, 1, 3},
        {10, 1, 10, 10, 10},
    }

    for _, tc := range testCases {
        fmt.Printf("Array: %v -> Minimum: %d\n", tc, findMinWithDuplicates(tc))
    }
}

The output for this variant:

Array: [2 2 2 0 1] -> Minimum: 0
Array: [1 3 3] -> Minimum: 1
Array: [3 3 1 3] -> Minimum: 1
Array: [10 1 10 10 10] -> Minimum: 1

Returning the Index Instead of the Value

Sometimes you need the index of the minimum element rather than its value. The modification is straightforward — simply return left instead of nums[left] at the end:

package main

import "fmt"

// findMinIndex returns the index of the minimum element.
func findMinIndex(nums []int) int {
    if len(nums) == 0 {
        panic("array must not be empty")
    }

    left, right := 0, len(nums)-1

    if nums[left] <= nums[right] {
        return left
    }

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

        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return left
}

func main() {
    nums := []int{4, 5, 6, 7, 0, 1, 2}
    idx := findMinIndex(nums)
    fmt.Printf("Minimum element %d is at index %d\n", nums[idx], idx)
}

Best Practices

Use Safe Mid Calculation

Always calculate the middle index as mid := left + (right-left)/2 rather than (left+right)/2. While Go's integers don't overflow as easily as some languages with fixed-width types, this habit prevents overflow bugs in languages like Java or C++ and makes your code more portable and readable across teams.

Handle Edge Cases Explicitly

Always account for edge cases such as empty arrays, single-element arrays, and already-sorted (non-rotated) arrays. The early return check if nums[left] <= nums[right] handles the non-rotated case efficiently and avoids unnecessary iterations.

Choose the Right Comparison Strategy

Comparing nums[mid] with nums[right] is generally cleaner than comparing with nums[left] because it avoids ambiguity. When comparing with the left, you need additional checks to handle the case where the left half is sorted but the rotation point is in the right half.

Write Comprehensive Tests

Always test your implementation against a variety of cases:

package main

import "testing"

func TestFindMin(t *testing.T) {
    tests := []struct {
        name     string
        nums     []int
        expected int
    }{
        {"rotated middle", []int{3, 4, 5, 1, 2}, 1},
        {"rotated at end", []int{2, 3, 4, 5, 1}, 1},
        {"not rotated", []int{1, 2, 3, 4, 5}, 1},
        {"single element", []int{1}, 1},
        {"two elements rotated", []int{2, 1}, 1},
        {"two elements sorted", []int{1, 2}, 1},
        {"rotated once", []int{5, 1, 2, 3, 4}, 1},
        {"large rotation", []int{6, 7, 8, 1, 2, 3, 4, 5}, 1},
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            result := findMin(tt.nums)
            if result != tt.expected {
                t.Errorf("findMin(%v) = %d, expected %d",
                    tt.nums, result, tt.expected)
            }
        })
    }
}

Avoid Recursion for Simple Cases

While a recursive solution is possible, the iterative approach is preferred in Go for this problem. It avoids function call overhead, prevents stack overflow on large inputs, and is more idiomatic in Go where simplicity and performance are valued.

Common Pitfalls to Avoid

Infinite loops: Using right = mid - 1 instead of right = mid can skip the minimum element. Since the minimum could be at mid, you must include it in the search space.
Off-by-one errors: The loop condition left < right (not left <= right) ensures termination when the pointers converge.
Ignoring the non-rotated case: Without the early check, the algorithm still works, but adding it improves clarity and handles the trivial case explicitly.
Assuming unique elements: If the problem allows duplicates, you must use the duplicate-aware variant to avoid incorrect results.

Complexity Analysis

For the standard version with unique elements:

Time complexity: O(log n) — each iteration halves the search space.
Space complexity: O(1) — only a few integer variables are used regardless of input size.

For the duplicate-handling variant:

Time complexity: O(log n) on average, but O(n) in the worst case (for example, an array of all identical elements except one).
Space complexity: O(1).

Conclusion

Solving the "Find Minimum in Rotated Sorted Array" problem in Go demonstrates the power and elegance of binary search when adapted to non-standard scenarios. By comparing the middle element with the rightmost element, you can reliably determine which half of the array contains the minimum, achieving an efficient O(log n) solution. The key takeaways are understanding the structural properties of rotated arrays, choosing the right comparison strategy, handling edge cases explicitly, and writing thorough tests. Whether you're preparing for interviews or building systems that work with circular data structures, mastering this pattern will strengthen your algorithmic thinking and give you a reliable tool for solving a family of related search problems in Go.