Recall & Review
beginner
What is the main idea behind the binary search algorithm?
Binary search works by repeatedly dividing a sorted list in half to find a target value quickly. It compares the target with the middle element and decides which half to search next.
Click to reveal answer
beginner
In the recursive binary search, what are the base cases?
The base cases are when the search range is empty (start index > end index), meaning the target is not found, or when the middle element equals the target, meaning the target is found.
Click to reveal answer
beginner
Why must the input array be sorted for binary search to work?
Binary search relies on the order of elements to decide which half to search next. If the array is not sorted, the algorithm cannot correctly eliminate half of the elements each time.
Click to reveal answer
intermediate
What is the time complexity of binary search and why?
The time complexity is O(log n) because each step cuts the search space in half, so the number of steps grows logarithmically with the size of the input.
Click to reveal answer
intermediate
Show the recursive call structure for binary search on array [2,4,6,8,10] searching for 8.
1. Check middle element (6 at index 2), 8 > 6, search right half [8,10].<br>2. Check middle element (8 at index 3), found target.<br>Recursive calls reduce search space until target is found.
Click to reveal answer
What should happen if the start index becomes greater than the end index in recursive binary search?
✗ Incorrect
When start > end, it means the search space is empty and the target is not present.
Which of these is NOT a requirement for binary search to work correctly?
✗ Incorrect
Binary search works with duplicates as well; uniqueness is not required.
What is the middle index calculation to avoid overflow in binary search?
✗ Incorrect
Using start + (end - start) / 2 prevents integer overflow.
If the middle element is less than the target, what part of the array does recursive binary search explore next?
✗ Incorrect
If middle element < target, search continues in the right half.
What is the worst-case time complexity of recursive binary search?
✗ Incorrect
Binary search halves the search space each time, leading to O(log n) complexity.
Explain how recursive binary search works step-by-step on a sorted array.
Think about how the problem size reduces each call.
You got /5 concepts.
Describe why binary search is more efficient than linear search on sorted arrays.
Focus on how many elements are checked in each approach.
You got /4 concepts.