Find Minimum in Rotated Sorted Array in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find minimum in rotated sorted array - simple case

What is the output of the following Go code that finds the minimum element in a rotated sorted array?

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
        } else {
            right = mid
        }
    }
    return nums[left]
}

func main() {
    arr := []int{4,5,6,7,0,1,2}
    fmt.Println(findMin(arr))
}

A 0

B 1

C 4

D 7

💡 Hint

Think about how the binary search narrows down the smallest element in a rotated array.

The code uses binary search to find the smallest element. Since the array is rotated, the smallest element is the pivot point. The code compares middle and right elements to decide which half to search next. The minimum is 0.

❓ Predict Output

intermediate

Find minimum in rotated sorted array - no rotation

What is the output of the following Go code when the array is not rotated?

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
        } else {
            right = mid
        }
    }
    return nums[left]
}

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

A 4

B 7

C 1

D 0

💡 Hint

If the array is sorted and not rotated, the first element is the smallest.

Since the array is sorted and not rotated, the smallest element is the first element, which is 1.

🔧 Debug

advanced

Identify the error in minimum finder for rotated array

What error does the following Go code produce when trying to find the minimum in a rotated sorted array?

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
        } else {
            right = mid - 1
        }
    }
    return nums[left]
}

func main() {
    arr := []int{4,5,6,7,0,1,2}
    fmt.Println(findMin(arr))
}

A infinite loop

B 0

C 7

D runtime error: index out of range

💡 Hint

Check how the pointers move and if they can go out of bounds.

The code decreases right by 1 even when it might skip the minimum element, causing left to go beyond array length and causing an index out of range error.

🧠 Conceptual

advanced

Why binary search works for finding minimum in rotated sorted array

Why does binary search work to find the minimum element in a rotated sorted array?

A Because the minimum element is always at the middle index

B Because the array is partially sorted and the minimum is the only point where order breaks

C Because the array is fully sorted and binary search always works on sorted arrays

D Because the array contains duplicates that help locate the minimum

💡 Hint

Think about the property of rotated sorted arrays and how order changes.

Binary search works because the rotated array is sorted except at the pivot point where the minimum lies. This break in order helps decide which half to search.

❓ Predict Output

expert

Find minimum in rotated sorted array with duplicates

What is the output of the following Go code that finds the minimum element in a rotated sorted array which may contain duplicates?

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
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            right--
        }
    }
    return nums[left]
}

func main() {
    arr := []int{2,2,2,0,1,2}
    fmt.Println(findMin(arr))
}

A 0

B 1

C 2

D runtime error

💡 Hint

Duplicates require careful handling to avoid skipping the minimum.

The code handles duplicates by reducing right when nums[mid] equals nums[right], ensuring the minimum is found. The minimum is 0.