Binary Search - C Plus Plus

Which statement best describes this call?
Answer: Its ordering requirement is violated, so its result cannot be relied upon. Whenever you see a question involving std::binary_search, your first instinct should be to check the precondition: the range must be partitioned with respect to the search value — essentially, it must be sorted (or at least arranged so that no element equivalent to the target appears after any element greater than it). Look at the vector: {2, 4, 8, 10, 6, 12}. The value $10$ appears before $6$ , which breaks the sorted order. std::binary_search is allowed to assume the range is ordered and uses that assumption to eliminate halves of the range without inspecting every element. When the precondition is violated, the algorithm may or may not find the target — the behavior is undefined in result, not just unpredictable by coincidence. This makes A correct: the ordering requirement is violated, so you cannot rely on the return value. B is wrong because the standard does not guarantee false — undefined behavior means the algorithm could return either true or false depending on implementation details and how the search unfolds. You can't predict which. C is wrong for the same reason in reverse. Just because $6$ physically exists in the container doesn't mean binary_search will find it. The algorithm may never even inspect that position. D is wrong because the ordering requirement applies to the entire range, not just the first and last elements. Checking only the endpoints is a classic trap — the interior must also be non-decreasing. Study tip: Always ask "Is this range sorted?" before reasoning about any algorithm from <algorithm> that has an ordering precondition (binary_search, lower_bound, upper_bound, merge). Endpoint-only checks will mislead you.
The sorted array is {3, 7, 11, 18, 24, 31, 42, 57, 63, 79, 88}. Which sequence of values is examined while searching for $57$ ?
Answer: $31, 63, 42, 57$ When tracing a binary search, you need to simulate the algorithm step by step, updating low and high based on comparisons. The array is {3, 7, 11, 18, 24, 31, 42, 57, 63, 79, 88} with indices 0–10. Step 1: low = 0, high = 10, so $mid = 0 + (10 - 0) / 2 = 5$ . The element at index 5 is 31. Since $57 > 31$ , you move right: low = 6. Step 2: low = 6, high = 10, so $mid = 6 + (10 - 6) / 2 = 8$ . The element at index 8 is 63. Since $57 < 63$ , you move left: high = 7. Step 3: low = 6, high = 7, so $mid = 6 + (7 - 6) / 2 = 6$ . The element at index 6 is 42. Since $57 > 42$ , you move right: low = 7. Step 4: low = 7, high = 7, so $mid = 7$ . The element at index 7 is 57 — found! This gives the sequence 31 → 63 → 42 → 57, confirming B is correct. Choice A skips 63 entirely, implying the algorithm jumped directly from 31 to 42, which is wrong. Choice C omits 42, skipping the step where the lower half is narrowed after examining 63. Choice D skips 31 as the first midpoint, starting from the wrong location. A useful strategy: always write out low, high, and mid for each iteration — students most commonly miss an examined element by rushing the simulation and skipping a step.
What can be concluded from that result alone?
Answer: At least one equivalent element exists, but no position or count is reported. When working with C++ search algorithms, it's crucial to understand exactly what each function promises — and what it deliberately leaves out. std::binary_search is a membership test, nothing more. It answers one yes/no question: does an equivalent element exist in the sorted range? That narrow contract is precisely why A is correct. The function returns true the moment it finds any element equivalent to the target via operator<. It tells you existence, but reports no position, no count, and no iterator. You cannot recover where the match was found or how many duplicates exist — that information simply isn't part of the return value. B is wrong because binary_search makes no claim about uniqueness. Finding true in a range with three 2s doesn't mean exactly one was present — it only confirms at least one was. C is wrong because binary_search returns a bool, not an iterator, so no iterator can be recovered from its result. If you need the position, you'd use std::lower_bound or std::upper_bound instead. D is wrong because binary search is specifically designed not to examine every element — it eliminates half the range each step, achieving O(log n) performance. Examining every occurrence would defeat the entire purpose of the algorithm. A useful mental model: think of binary_search as the existence-only tool, lower_bound/upper_bound as the position tools, and equal_range as the count/range tool. On C++ exams, questions about these often test whether you conflate what each one actually returns — so always ask yourself, "what does this function's return type even allow it to tell me?"
Which modification preserves the ordering required for that binary search?
Answer: Insert $20$ immediately after the element $19$ . Whenever you see a question involving std::binary_search, the first thing to check is whether the range satisfies the sorted precondition. Binary search requires the elements to be ordered according to the comparison operator — with the default <, that means non-decreasing order. If the sequence isn't sorted, the behavior is undefined and results are meaningless. The original vector is {5, 12, 19, 27, 34}. After inserting $20$ immediately after $19$ , you get {5, 12, 19, 20, 27, 34} — still perfectly sorted in ascending order. Binary search can now correctly locate $34$ . This makes C the correct answer. A is wrong because appending $20$ to the end produces {5, 12, 19, 27, 34, 20}. The value $20$ comes after $34$ , breaking the sorted order entirely — binary search on this sequence has undefined behavior. B is wrong because inserting $20$ before $19$ gives {5, 12, 20, 19, 27, 34}. Now $20 > 19$ but appears earlier, which violates the non-decreasing requirement and corrupts the search. D is wrong because reversing the vector produces {34, 27, 19, 12, 5}, a descending sequence. std::binary_search with its default comparator expects ascending order, not descending. You would need to pass std::greater<int>{} as a custom comparator to search a reversed range — which the question doesn't do. Study tip: Always ask yourself, "Is the container sorted in a way that matches the comparator?" before applying any binary search algorithm. The algorithm trusts you — it won't verify ordering for you.
What does the call return?
Answer: true, because "bee" and "BEE" are equivalent under ciLess. When you see a question about std::binary_search with a custom comparator, the key insight is understanding how the algorithm defines "equivalence." Binary search doesn't use operator== to check if an element matches — it uses the comparator itself. Two values a and b are considered equivalent if !comp(a, b) && !comp(b, a): neither comes before the other under the ordering. Since ciLess compares strings case-insensitively, "bee" and "BEE" are neither less than each other — so ciLess("bee", "BEE") is false and ciLess("BEE", "bee") is also false. That means they are equivalent under ciLess, and binary_search returns true. D is correct. A is wrong because it assumes binary_search checks for exact stored values using ==. It doesn't — it uses the comparator's equivalence relation, not identity. B is wrong for the same reason. Normal string equality ("bee" == "BEE") is indeed false, but binary_search never calls operator==. This is the most tempting distractor because it sounds technically precise, but it misidentifies which comparison actually happens. C is wrong because the vector is sorted according to ciLess — the problem states this explicitly. Case-insensitive sorting places "Ant", "bee", "Cat", "dog" in valid order under that comparator, so the precondition for binary_search is satisfied. Study tip: Whenever you use STL algorithms with custom comparators, remember the rule: the same comparator must define both the sort order and the equivalence check. Mixing a custom sort with default equality is a classic bug — and a classic exam trap.
What happens?
Answer: It repeats with the same lower midpoint and does not terminate. When you see a binary search question, your instinct should be to trace the index updates carefully — subtle off-by-one errors in low and high assignments are a classic source of infinite loops. Here, the bug is in the low = mid update. Standard binary search requires low = mid + 1 when a[mid] < key, so the search range strictly shrinks. Let's trace this with {2, 5, 9, 14} and key = 15: - Iteration 1: low=0, high=3, mid = 0 + 3/2 = 1. a[1]=5 < 15, so low = mid = 1. - Iteration 2: low=1, high=3, mid = 1 + 2/2 = 2. a[2]=9 < 15, so low = mid = 2. - Iteration 3: low=2, high=3, mid = 2 + 1/2 = 2. a[2]=9 < 15, so low = mid = 2 again. Now you're stuck: low, high, and mid never change. The loop condition low <= high remains true forever, and the function never terminates — confirming D. A is wrong because the function doesn't visit every element once and exit cleanly; it gets trapped revisiting index 2. B is wrong because the range never becomes empty — low never surpasses high. C is wrong because the index never exceeds 3; out-of-bounds access isn't the issue here. Study tip: Whenever you review a binary search implementation, always verify that both low and high update to values that guarantee the range strictly shrinks — low = mid + 1 and high = mid - 1 are the standard safe assignments.
Which midpoint expression avoids overflow from adding the two indices and computes the lower midpoint?
Answer: low + (high - low) / 2 Whenever you see a question about index arithmetic in C++, your first instinct should be to check whether any intermediate value can exceed INT_MAX — because signed integer overflow is undefined behavior, not just a wrong number. The safe approach is C: low + (high - low) / 2. Since low <= high, the subtraction high - low is guaranteed non-negative and fits within int range (it's at most INT_MAX). Dividing that by 2 keeps it smaller, and adding low back produces a value in [low, high]. No overflow is possible at any step, and you get the lower midpoint (the one closer to low when the two middle elements exist). A — (low + high) / 2 — is the classic trap. If both low and high are near INT_MAX, their sum wraps around (undefined behavior in C++), producing a negative or garbage result. This is exactly the bug famously found in Java's Arrays.sort and many C binary-search implementations. B — low / 2 + high / 2 — avoids overflow but introduces a different error: if both values are odd, each loses 0.5 in truncation, so the result is one less than the true midpoint. It silently computes the wrong index. D — low + (high - low + 1) / 2 — is safe from overflow, but the +1 before dividing biases the result upward, giving the upper midpoint. This matters in certain binary-search variants, so it's the right formula in the wrong situation here. Study tip: Memorize low + (high - low) / 2 as your default safe midpoint — it's a pattern that appears constantly in competitive programming and interview questions alike.
For a sorted range containing $1000$ elements, what is the maximum number of midpoint examinations needed to determine whether a target is present?
Answer: $10$ midpoint examinations Whenever you see a question about binary search, your core tool is the logarithm base 2. Binary search works by repeatedly halving the search range — each examination eliminates half the remaining elements, so the maximum number of steps needed to search $n$ elements is $\lceil \log_2 n \rceil$ . For $n = 1000$ , calculate $\log_2 1000$ . Since $2^{10} = 1024$ and $2^9 = 512$ , we know $\log_2 1000 \approx 9.97$ . Because you can't perform a fractional examination, you round up to the nearest whole number, giving you $\lceil 9.97 \rceil = 10$ . After 10 midpoint checks, the range has been narrowed down to at most one element — confirming or denying the target's presence. This makes B) 10 midpoint examinations correct. Choice A) 9 is tempting because $2^9 = 512$ , which covers up to 512 elements — not quite enough for 1000. Students who truncate instead of ceiling the logarithm fall into this trap. Choice C) 11 would be correct for a range up to $2^{11} = 2048$ elements; it's one step too many for 1000 elements, likely chosen by students who round up too aggressively. Choice D) 500 reflects a linear thinking mistake — imagining you always check half the list rather than understanding the logarithmic shrinkage. A linear scan of half the list would be 500 checks, which is closer to a worst-case sequential search, not binary search. Your quick study tip: memorize the key powers of 2 ( $2^9 = 512$ , $2^{10} = 1024$ , $2^{11} = 2048$ ) and always apply the ceiling function — binary search complexity is $\lceil \log_2 n \rceil$ , never truncated.
What value is assigned to found, and why?
Answer: false, because the searched range contains only $9, 15, 22$ . When working with STL algorithms like std::binary_search, the most critical detail is understanding how iterator ranges work. In C++, range-based algorithms always follow a half-open interval convention: [begin, end), meaning the element pointed to by the end iterator is excluded from the range. Given v{4, 9, 15, 22, 31, 40}, the indices are 0–5. v.begin() + 1 points to index 1 (value $9$ ), and v.begin() + 4 points to index 4 (value $31$ ). Because the end iterator is exclusive, the searched range covers only indices 1, 2, and 3 — the values $\{9, 15, 22\}$ . Since $31$ is not in that range, binary_search returns false, making C correct. A is wrong because binary_search doesn't scan the entire vector — it only inspects the explicitly provided subrange. The position of $31$ relative to end() is irrelevant. B reflects a common misconception: the second iterator does not mark the last included element; it marks the first excluded element. If you wanted to include index 4, you'd write v.begin() + 5. D is simply false — std::binary_search works correctly on any valid subrange regardless of where it starts, as long as that subrange is sorted. As a study tip, burn the half-open interval rule into memory: every STL range is [first, last). When you see iterator arithmetic, always ask yourself which element last points to — and remember it's never included.
Which call searches the full range using an ordering consistent with v and returns true?
Answer: std::binary_search(v.begin(), v.end(), 45, std::greater<int>{}) When working with std::binary_search, two conditions must both be satisfied for a call to be valid and return true: the range must be sorted according to the comparator you provide, and the value must exist in that range. The vector v{90, 75, 60, 45, 30, 15} is sorted in descending order. This is critical — std::binary_search assumes the range is ordered consistently with whatever comparator you pass. If you use std::greater<int>{}, you're telling the algorithm "this range is sorted largest-to-smallest," which matches v perfectly. The value 45 exists in v, so A correctly searches the full range with a matching comparator and finds the element, returning true. B fails because it uses the default comparator (std::less<int>{}), which assumes ascending order. Applying it to a descending vector produces undefined behavior — you cannot rely on it returning true even if 45 is present. C uses the correct comparator std::greater<int>{} and searches the full range, but it searches for 50, which does not exist in v. Binary search can only return true for values actually present, so C returns false. D uses the correct comparator and searches for 45, but it only covers v.begin() to v.begin() + 3, which includes {90, 75, 60}. The value 45 falls outside this subrange, so D also returns false. A quick rule to memorize: comparator and sort order must match, and the value must be in the searched range. Always check both conditions together.

Start this quiz