Bitkernel·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Bitkernel had a binary search question that looked straightforward but was actually a trap for anyone who hadn't thought carefully about how the algorithm narrows its search window. Short round, one question, left me second-guessing myself.

Questions Asked (1)

Given a sorted array containing the keys 180, 200, 450, and 500, which of the following sequences of comparisons cannot occur during a single run of binary search: (A) 500, 200, 450, 180 (B) 500, 450, 200, 180 (C) 180, 500, 200, 450 (D) 180, 200, 500, 450?

Algorithms & Data Structures

Author's notes

I stared at this longer than I'd like to admit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Simulate binary search on the sorted array [180, 200, 450, 500] and track the possible midpoints at each step. For each sequence, verify whether each comparison could be the midpoint of the current search interval, pruning the interval accordingly. The sequence that violates the binary search invariant is the answer.

Pro tip: Remember that binary search always compares the middle element of the current subarray; the first comparison must be either 200 or 450 (the two possible midpoints of the full array). This immediately eliminates sequences starting with 500 or 180, but be careful: some sequences may still be possible if the array size is even and the midpoint choice varies.

1. Understand binary search mechanics

Recall that binary search compares the target with the middle element of the current search interval, then discards the half that cannot contain the target. The midpoint is typically floor((low+high)/2).

2. Identify possible first comparisons

For the full array of 4 elements (indices 0-3), the middle index is floor((0+3)/2)=1, so the first comparison must be 200. If using a different midpoint convention (e.g., ceiling), it could be 450. Thus, any valid sequence must start with 200 or 450.

3. Simulate each sequence

For each option, start with the full array and check if the first element matches a possible midpoint. Then update the search interval based on whether the target is less than or greater than the compared key, and continue.

4. Check consistency with sorted order

At each step, ensure the compared key is the middle of the current interval. If a sequence requires a comparison that is not the middle of the remaining elements, it cannot occur.

5. Determine the invalid sequence

After simulating all sequences, identify the one that violates the binary search invariant. Typically, this is the sequence that starts with an element that cannot be the first midpoint.

Key Points to Mention

Binary search requires the array to be sorted.
The midpoint is calculated as floor((low+high)/2) (or ceiling, depending on implementation).
The first comparison must be the middle element of the full array.
After each comparison, the search interval is halved.
The sequence of comparisons must respect the sorted order and the halving process.
For an array of size 4, the possible first midpoints are indices 1 and 2 (values 200 and 450).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.