Binary Search Quiz: Test Your AP Computer Science A Knowledge

📚 Quick Study Guide

• 🔍 Binary search is an efficient algorithm for finding a target value within a sorted array.
• ⏱️ The time complexity of binary search is $O(\log n)$, where $n$ is the number of elements in the array. This makes it significantly faster than linear search for large datasets.
• ➗ The core idea is to repeatedly divide the search interval in half.
• 🎯 Binary search requires the input array to be sorted. If the array is not sorted, you must sort it first, which typically takes $O(n \log n)$ time.
• ✏️ The algorithm maintains three variables: low, high, and mid, representing the lower bound, upper bound, and middle element of the search interval, respectively.
• 💡 Common implementations involve iterative or recursive approaches.
• ⚠️ Be careful when calculating the middle index to avoid integer overflow: use mid = low + (high - low) / 2 instead of mid = (low + high) / 2.
• 📈 If the target is less than the middle element, the search continues in the left half of the array. If the target is greater, the search continues in the right half.

🧪 Practice Quiz

1. Which of the following is a prerequisite for applying binary search on an array?
   1. The array must be sorted.
   2. The array must contain only positive numbers.
   3. The array must be of even length.
   4. The array must not contain duplicate elements.
2. What is the time complexity of binary search in the worst-case scenario?
   1. $O(n)$
   2. $O(\log n)$
   3. $O(n^2)$
   4. $O(n \log n)$
3. In binary search, what happens if the target element is less than the middle element?
   1. The search continues in the right half of the array.
   2. The search continues in the left half of the array.
   3. The search stops and returns the middle element's index.
   4. The search starts from the beginning of the array.
4. Which of the following is the correct way to calculate the middle index in binary search to avoid potential integer overflow?
   1. mid = (low + high) / 2
   2. mid = low + (high - low) / 2
   3. mid = high - (high - low) / 2
   4. mid = (low + high) >> 1
5. What is the space complexity of binary search (iterative implementation)?
   1. $O(n)$
   2. $O(\log n)$
   3. $O(1)$
   4. $O(n \log n)$
6. Binary search is best suited for:
   1. Searching a linked list.
   2. Searching an unsorted array.
   3. Searching a sorted array.
   4. Inserting elements into an array.
7. What is the best-case time complexity of binary search?
   1. $O(1)$
   2. $O(\log n)$
   3. $O(n)$
   4. $O(n \log n)$