Questions: Binary Search

Question 1

You run binary search on an array that you believe is sorted, but it was accidentally left unsorted. The target value is present. What will happen?

• A. Binary search will still find the target — it checks all elements eventually
• B. Binary search will return an error because it detects the unsorted order
• C. Binary search may fail to find the target and return 'not found' even though it is present
• D. Binary search will find the target but will be slower than linear search

Answer: (C)

Binary search relies on a critical guarantee: if the target is less than the middle element, it cannot be in the right half. This inference is only valid if the array is sorted. On an unsorted array, the target could be anywhere — including in the half that binary search has just eliminated. The algorithm may confidently discard the half containing the target and return 'not found' even when the target is present. This is not a performance issue but a correctness issue: binary search on unsorted data produces wrong answers, not just slow ones. Always verify that the input is sorted before applying binary search.

Question 2

Why does binary search achieve O(log n) time complexity?

• A. Because it uses two pointers that move toward each other, halving the work at each step
• B. Because each comparison eliminates half the remaining candidates, reducing n elements to 1 in at most log₂(n) comparisons
• C. Because the midpoint calculation takes O(log n) time on modern hardware
• D. Because it only checks elements at positions that are powers of 2

Answer: (B)

After k comparisons, the search space has been halved k times, leaving n/2^k elements. The algorithm terminates when this reaches 1 (or 0 if the element is absent), so we solve n/2^k = 1 to get k = log₂(n). For n = 1,000,000, that is about 20 comparisons. Linear search, by contrast, may check all n elements. The log comes directly from the repeated halving — which is only possible because sortedness lets you definitively eliminate entire halves. The two-pointer movement in option A is a correct description of *how* binary search works, but the O(log n) complexity comes from the *halving*, not from the pointers per se.

Question 3

Binary search can be applied to any problem where a monotonic predicate divides the search space into 'yes' and 'no' regions, not just to sorted arrays.

• T. True
• F. False

Answer: True

The sorted array is just one instance of a general principle: binary search applies wherever there is a monotonic predicate — a yes/no question where all 'yes' answers come before all 'no' answers (or vice versa) across the search space. For example, 'does k workers suffice to handle this load?' may be monotonic: once k is large enough (yes), all larger values also suffice. The smallest satisfying k can be binary searched. 'What is the smallest radius that contains all points?' — similarly monotonic. This generalization, called binary search on the answer, is one of the most powerful algorithmic techniques and appears in competitive programming and system design alike.

Question 4

Binary search can be applied to any array, sorted or not, as long as you know the target value you're looking for.

• T. True
• F. False

Answer: False

Sorting is not a convenience — it is a correctness requirement. Binary search's logic depends entirely on the inference: 'if target < a[mid], the target cannot be in a[mid+1..high].' This inference is only valid when the array is sorted. On an unsorted array, the target could be anywhere, and eliminating half the array based on a midpoint comparison is incorrect. The algorithm will produce wrong answers on unsorted input — not slower correct answers. If you need to search an unsorted collection, you must either sort it first (then binary search works in O(n log n) + O(log n)) or use linear search in O(n).

Question 5

What property of a sorted array allows binary search to eliminate half the candidates with a single comparison, and why does the same principle not apply to an unsorted array?

Model answer: In a sorted array, the ordering guarantee means that all elements to the left of any position are smaller and all elements to the right are larger. When we compare the target to the middle element, this guarantee lets us draw an absolute conclusion: if the target is smaller, it cannot exist anywhere in the right half (since every element there is larger than the middle). We have eliminated half the candidates with a single comparison and zero further inspection. In an unsorted array, no such guarantee exists: the target could be anywhere regardless of how it compares to the middle element, so we can eliminate nothing and must check everything.

The key concept is information content of a comparison. In a sorted array, a single comparison carries log₂(n) bits of information — it tells you which half to search. In an unsorted array, a comparison tells you only whether the middle element matches or not — no information about the other n−1 elements. The entire efficiency of binary search is derived from this information amplification, which exists only when the array is sorted.