Recall & Review
beginner
What is a rotated sorted array?
A rotated sorted array is an array that was originally sorted in ascending order but then rotated (shifted) at some pivot point. For example, [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7].
Click to reveal answer
beginner
Why can't we just scan the entire rotated sorted array to find the minimum?
Scanning the entire array takes O(n) time. Using a special approach like binary search can find the minimum in O(log n) time, which is faster for large arrays.
Click to reveal answer
intermediate
What is the key idea behind using binary search to find the minimum in a rotated sorted array?
We compare the middle element with the rightmost element to decide which half contains the minimum. If middle is greater than right, minimum is in the right half; else, it's in the left half.
Click to reveal answer
intermediate
What is the stopping condition in the binary search for finding the minimum in a rotated sorted array?
When the search space reduces to one element, that element is the minimum.
Click to reveal answer
intermediate
Show the Go code snippet to find the minimum in a rotated sorted array using binary search.
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]
}
Click to reveal answer
What does a rotated sorted array look like?
✗ Incorrect
A rotated sorted array is a sorted array shifted at some pivot, like [4,5,6,7,0,1,2].
What is the time complexity of binary search to find the minimum in a rotated sorted array?
✗ Incorrect
Binary search reduces the search space by half each time, so it runs in O(log n) time.
In the binary search, if nums[mid] > nums[right], where is the minimum?
✗ Incorrect
If nums[mid] > nums[right], minimum must be in the right half excluding mid.
What happens when left == right in the binary search for minimum?
✗ Incorrect
When left equals right, the search space is one element, which is the minimum.
Which of these is the correct Go function signature to find minimum in rotated sorted array?
✗ Incorrect
The function takes a slice of integers and returns an integer minimum.
Explain how binary search helps find the minimum in a rotated sorted array.
Think about which half to keep based on mid and right values.
You got /4 concepts.
Write the steps to find the minimum in [4,5,6,7,0,1,2] using binary search.
Trace the indexes and values carefully at each step.
You got /6 concepts.