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, which is slower. Using the special property of rotation, we can find the minimum in O(log n) time using a binary search approach.
Click to reveal answer
intermediate
In the binary search for minimum in rotated sorted array, what does it mean if the middle element is greater than the rightmost element?
It means the minimum is in the right half of the array because the rotation point is to the right of mid.
Click to reveal answer
beginner
What is the stopping condition in the binary search to find 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 binary search steps to find the minimum in [4,5,6,7,0,1,2].
Start: left=0, right=6
mid=3 (value=7) > right=6 (value=2) → minimum in right half → left=mid+1=4
Now left=4, right=6
mid=5 (value=1) < right=6 (value=2) → minimum in left half including mid → right=mid=5
Now left=4, right=5
mid=4 (value=0) < right=5 (value=1) → right=mid=4
left=4, right=4 → stop, minimum=0 at index 4
Click to reveal answer
What is the time complexity of finding the minimum in a rotated sorted array using binary search?
✗ Incorrect
Binary search divides the search space in half each time, leading to O(log n) time.
If the middle element is less than the rightmost element in the rotated array, where is the minimum?
✗ Incorrect
If mid < right, the minimum lies in the left half including mid.
What does it mean if the array is not rotated?
✗ Incorrect
If the array is sorted and not rotated, the first element is the smallest.
Which of these arrays is a rotated sorted array?
✗ Incorrect
A is descending sorted; B is sorted but not rotated; C is rotated sorted ascending; D is unsorted.
What is the minimum element in [6,7,1,2,3,4,5]?
✗ Incorrect
1 is the smallest element after rotation.
Explain how binary search helps find the minimum in a rotated sorted array.
Think about how rotation affects order and how to narrow down the search.
You got /4 concepts.
Describe the characteristics of a rotated sorted array and how it differs from a normal sorted array.
Imagine a sorted list shifted like a clock hand.
You got /4 concepts.