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.

Practice

1. What is the main idea behind finding the minimum element in a rotated sorted array?

easy

A. Use a hash map to store elements and find minimum

B. Sort the array again to find the minimum

C. Traverse the array linearly to find the smallest element

D. Use binary search to find the point where order breaks

Solution

1. Step 1: Understand the rotated sorted array property

   A rotated sorted array is sorted but rotated at some pivot point, causing a break in order.

2. Step 2: Use binary search to find the break point

   Binary search helps find the point where the order breaks, which is where the minimum element lies.

3. Final Answer:

   Use binary search to find the point where order breaks -> Option D

4. Quick Check:

   Binary search finds minimum efficiently [OK]

Hint: Look for the pivot where order breaks using binary search [OK]

Common Mistakes:

• Trying to sort the array again wastes time
• Using linear search ignores the sorted property
• Using extra space unnecessarily

2. Which Go code snippet correctly initializes variables for binary search to find minimum in a rotated sorted array nums?

easy

A. start, end := -1, len(nums)-1

B. start, end := 0, len(nums)-1

C. start, end := 1, len(nums)

D. start, end := 0, len(nums)

Solution

1. Step 1: Understand array indexing in Go

   Arrays are zero-indexed, so start should be 0 and end should be last index (length - 1).

2. Step 2: Check each option for correct initialization

   start, end := 0, len(nums)-1 correctly sets start=0 and end=len(nums)-1, which is valid for binary search.

3. Final Answer:

   start, end := 0, len(nums)-1 -> Option B

4. Quick Check:

   Correct index range initialization [OK]

Hint: Start at 0 and end at length minus one for array indices [OK]

Common Mistakes:

• Using length as end index causes out-of-range errors
• Starting at 1 misses the first element
• Negative start index is invalid

3. What will be the output of the following Go code snippet?

nums := []int{4,5,6,7,0,1,2}
start, end := 0, len(nums)-1
for start < end {
  mid := (start + end) / 2
  if nums[mid] > nums[end] {
    start = mid + 1
  } else {
    end = mid
  }
}
fmt.Println(nums[start])

medium

A. 0

B. 4

C. 7

D. 2

Solution

1. Step 1: Trace the binary search loop

   Initial start=0, end=6. Mid=(0+6)/2=3, nums[3]=7 > nums[6]=2, so start=4.

2. Step 2: Continue loop until start meets end

   Now start=4, end=6. Mid=(4+6)/2=5, nums[5]=1 <= nums[6]=2, so end=5. Next mid=(4+5)/2=4, nums[4]=0 <= nums[5]=1, so end=4. Loop ends when start=4, end=4.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Minimum element found at index 4 is 0 [OK]

Hint: Compare mid with end to decide search side [OK]

Common Mistakes:

• Confusing mid calculation causing infinite loop
• Incorrectly updating start or end pointers
• Printing nums[end] instead of nums[start]

4. Identify the bug in this Go code to find minimum in rotated sorted array nums:

start, end := 0, len(nums)-1
for start <= end {
  mid := (start + end) / 2
  if nums[mid] > nums[end] {
    start = mid
  } else {
    end = mid - 1
  }
}
fmt.Println(nums[start])

medium

A. All of the above

B. Loop condition should be start < end, not <=

C. end should be set to mid, not mid - 1

D. start should be set to mid + 1, not mid

Solution

1. Step 1: Analyze loop condition and pointer updates

   The loop uses start <= end which can cause infinite loop when start == end. Also, start = mid does not move start forward properly, and end = mid - 1 skips the mid element incorrectly.

2. Step 2: Correct the loop and pointer updates

   Loop should be start < end. When nums[mid] > nums[end], start = mid + 1 to move forward. Else, end = mid to include mid in next search.

3. Final Answer:

   All of the above -> Option A

4. Quick Check:

   Proper loop and pointer updates avoid infinite loops [OK]

Hint: Use start < end and adjust pointers by +1 or no change [OK]

Common Mistakes:

• Using <= causes infinite loops
• Not moving start pointer forward correctly
• Skipping mid element by subtracting 1 from end

5. Given a rotated sorted array nums that may contain duplicates, which modification is needed in the binary search approach to find the minimum element?

hard

A. Ignore duplicates and apply normal binary search

B. If nums[mid] == nums[end], increase start by 1 to skip duplicate

C. If nums[mid] == nums[end], reduce end by 1 to skip duplicate

D. Sort the array first to handle duplicates

Solution

1. Step 1: Understand duplicates affect binary search

   Duplicates can cause nums[mid] == nums[end], making it unclear which side to search.

2. Step 2: Modify binary search to handle duplicates

   When nums[mid] == nums[end], safely reduce end by 1 to skip duplicate without missing minimum.

3. Final Answer:

   If nums[mid] == nums[end], reduce end by 1 to skip duplicate -> Option C

4. Quick Check:

   Handle duplicates by shrinking search space carefully [OK]

Hint: When equal, reduce end to skip duplicates safely [OK]

Common Mistakes:

• Ignoring duplicates causes wrong results
• Increasing start instead of reducing end misses minimum
• Sorting wastes time and is unnecessary