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 use simple binary search directly on a rotated sorted array?
Because the array is not fully sorted in ascending order due to rotation, simple binary search may fail. The array has two sorted parts separated by the pivot, so we need to identify which part to search in.
Click to reveal answer
intermediate
In the search algorithm for a rotated sorted array, how do we decide which half to search next?
We check if the left half is sorted by comparing the start and middle elements. If it is sorted and the target lies within it, we search left. Otherwise, we search right. If the left half is not sorted, the right half must be sorted, so we check if the target lies there.
Click to reveal answer
beginner
What is the time complexity of searching in a rotated sorted array using the modified binary search?
The time complexity is O(log n) because each step halves the search space, similar to normal binary search.
Click to reveal answer
intermediate
Show the Go code snippet for searching a target in a rotated sorted array using binary search.
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
}
if nums[left] <= nums[mid] {
if nums[left] <= target && target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else {
if nums[mid] < target && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}
Click to reveal answer
What is the main challenge when searching in a rotated sorted array?
✗ Incorrect
The rotation breaks the full ascending order, so normal binary search cannot be applied directly.
If nums[left] <= nums[mid], what does it tell us about the array segment from left to mid?
✗ Incorrect
If the left element is less than or equal to mid element, that segment is sorted.
What should you do if the target is not in the sorted half of the array during search?
✗ Incorrect
If the target is not in the sorted half, it must be in the other half.
What is the return value if the target is not found in the rotated sorted array?
✗ Incorrect
The function returns -1 to indicate the target is not found.
What is the time complexity of the search algorithm in a rotated sorted array?
✗ Incorrect
The algorithm halves the search space each step, so it runs in logarithmic time.
Explain how to search for a target in a rotated sorted array using binary search.
Think about how rotation splits the array into two sorted parts.
You got /5 concepts.
Describe the difference between normal binary search and binary search on a rotated sorted array.
Focus on how rotation affects sorting and search decisions.
You got /5 concepts.