Find Minimum in Rotated Sorted Array in DSA Go

Mental Model

A rotated sorted array is like a sorted list that has been shifted. The smallest number is where the shift happened. We find it by checking the middle and deciding which half to search next.

Analogy: Imagine a clock face turned clockwise by some hours. The smallest number is where the clock starts again at 1 after the rotation.

Original sorted array:
[1] -> [2] -> [3] -> [4] -> [5] -> null

Rotated array example:
[4] -> [5] -> [1] -> [2] -> [3] -> null
          ↑ (rotation point, smallest element)

Dry Run Walkthrough

Input: array: [4, 5, 1, 2, 3]

Goal: Find the smallest number in the rotated sorted array

Step 1: Set left=0, right=4, find mid=(0+4)/2=2

[4] -> [5] -> [1] -> [2] -> [3]
 left=0, mid=2, right=4

Why: We start by checking the middle element to decide which half to search

Step 2: Compare nums[mid]=1 with nums[right]=3; since 1 < 3, move right to mid

[4] -> [5] -> [1] -> [2] -> [3]
 left=0, mid=2, right=2

Why: Minimum must be in left half including mid because mid is smaller than right

Step 3: Calculate new mid=(0+2)/2=1

[4] -> [5] -> [1] -> [2] -> [3]
 left=0, mid=1, right=2

Why: We narrow search to left half to find minimum

Step 4: Compare nums[mid]=5 with nums[right]=1; since 5 > 1, move left to mid+1

[4] -> [5] -> [1] -> [2] -> [3]
 left=2, mid=1, right=2

Why: Minimum must be in right half excluding mid because mid is greater than right

Step 5: Now left=2 equals right=2, stop search

[4] -> [5] -> [1] -> [2] -> [3]
 left=2, right=2

Why: When left meets right, we found the smallest element

Result:

Final state: [4] -> [5] -> [1] -> [2] -> [3]
Minimum element is nums[2] = 1

Annotated Code

DSA Go

package main

import "fmt"

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1 // minimum is in right half
        } else {
            right = mid // minimum is in left half including mid
        }
    }
    return nums[left] // left == right is minimum
}

func main() {
    nums := []int{4, 5, 1, 2, 3}
    min := findMin(nums)
    fmt.Println(min)
}

for left < right {

loop until search space narrows to one element

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

calculate middle index to split search space

if nums[mid] > nums[right] {

if middle element is greater than right, minimum is in right half

left = mid + 1 // minimum is in right half

move left pointer to mid+1 to discard left half

right = mid // minimum is in left half including mid

else move right pointer to mid to keep left half

return nums[left] // left == right is minimum

return the minimum element found

Output

1

Complexity Analysis

Time: O(log n) because the search space halves each iteration

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to scanning all elements O(n), this binary search approach is much faster for large arrays

Edge Cases

Array not rotated (e.g., [1, 2, 3, 4, 5])

Algorithm returns the first element as minimum

DSA Go

if nums[mid] > nums[right] {

Array with single element (e.g., [10])

Returns that element immediately as minimum

DSA Go

for left < right {

Array rotated at last element (e.g., [2, 3, 4, 5, 1])

Algorithm correctly finds the smallest element at the end

DSA Go

if nums[mid] > nums[right] {

When to Use This Pattern

When you see a sorted array that might be rotated and need the smallest element, use binary search to find the rotation point efficiently.

Common Mistakes

Mistake: Using nums[mid] >= nums[right] instead of nums[mid] > nums[right], causing infinite loop when duplicates exist
Fix: Use strict greater than '>' to correctly narrow search space

Summary

Finds the smallest element in a rotated sorted array using binary search.

Use when you have a sorted array shifted at some pivot and want the minimum quickly.

The key is comparing middle and right elements to decide which half contains the minimum.