MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Coding Interview Patterns Module 9

Binary search interview questions

Interview questions on binary search: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

28 questions: 4 warm-ups and 24 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

  1. Fresher to mid

    Which two bounds count the values of a sorted list that lie in a closed range [a, b], and which two count them in a half-open range [a, b)?

    Answered in the lesson First, last and count with bounds

  2. Fresher to mid

    What is a rotated sorted array, and why is it still a good input for binary search although it is not sorted?

    A rotated sorted array is a sorted array cut once, with the two pieces swapped: the sorted list 8, 15, 23, 30, 41, 47, 52 cut before 41 becomes [41, 47, 52, 8, 15, 23, 30]. It consists of two sorted runs, and every value of the second run is smaller than every value of the first; an array that was never rotated is a single run. That structure is what binary search needs. The question "is position i in the second run?" is answered no up to the smallest value and yes from there on, so the answer flips exactly once, and finding where it flips takes O(log n) comparisons instead of the n of a scan.

    From the lesson Rotated arrays and peaks

  3. Fresher to mid

    In a grid whose rows and columns are both sorted, which corner should a search for a value start from, and what does that choice buy?

    Start at the top-right corner. Its cell is the largest value of its row and the smallest value of its column, so one comparison with the value you want rules out a whole row or a whole column: whatever the answer, a line of the grid can no longer hold the value. Every read therefore removes a row or a column, and the search finishes within rows + columns − 1 reads, instead of the rows × columns reads of checking every cell. On a grid of 2,000 by 2,000 that is at most 3,999 reads instead of 4,000,000.

    From the lesson Sorted matrices: staircase and value search

  4. Fresher to mid

    What is the median of two sorted arrays when the total number of values is even, and what does a merge cost to find it?

    The median is the middle value of all the values of both arrays together. When the total is even there are two middle values, and the median is their mean: for [5, 8] and [1, 2, 3, 9] the six values in order are 1, 2, 3, 5, 8 and 9, so the median is (3 + 5) / 2 = 4. A merge walks both arrays in order, always taking the smaller next value, and stops at the middle, so it reads about (m + n) / 2 + 1 values with O(1) extra memory. That is O(m + n) time: fine for small arrays, but a binary search over where to cut the shorter array needs only O(log min(m, n)).

    From the lesson Partition search: median of two sorted arrays

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

  1. Mid to senior

    A sorted log holds 5 × 10⁷ event times from one day, in milliseconds. You must answer 10⁶ questions of the form "how many events between t1 and t2?" in about a second of CPU time. Compare two bounds per question, a counting table and sorting the questions, with time and memory figures, and choose.

    What it tests
    Estimating the time and memory of three range-count designs, seeing that the key range decides whether a table fits, and choosing with numbers rather than by habit.
    First step
    Size each option before choosing. Two bounds cost about 2 × 26 = 52 halving steps per question, so about 5 × 10⁷ steps in all. A table needs one count for every millisecond of the day, 86,400,000 of them: work out the bytes before deciding whether it fits.
    Follow-ups

    From the lesson First, last and count with bounds

    Opening the model answers with your pass…

    Model answers open with any MySmartCoPilot pass.

    • Pro pass · 1 week₹79$2.99
    • 30 days₹179$5.99
    • 1 year₹1,699$45

    One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

    Choose a passI have a licence key

    It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  2. Fresher to mid

    Your function returns the first and the last index of x in a sorted array with two binary searches. It passes the samples, but hidden tests report a wrong last index on some inputs and an index error on others. What are the likely bugs, and which small tests expose each one?

    What it tests
    Debugging boundary code from its symptoms: the upper bound against the last index, empty blocks and arrays, a bound equal to n, and designing the smallest tests that fail.
    First step
    Say what each search returns as a position, not a value: the lower bound is the first index with a[i] ≥ x and the upper bound the first with a[i] > x. Then list the inputs where a bound can be 0 or n, or the block can be empty, and work each one by hand.
    Follow-ups

    From the lesson First, last and count with bounds

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  3. Mid to senior

    Values arrive one at a time, and between arrivals you are asked how many values so far lie in [a, b]. There are 2 × 10⁵ arrivals and 2 × 10⁵ questions, with values up to 10⁹. Why is a sorted list with insertion too slow, and what do you use instead?

    What it tests
    Seeing the linear cost of keeping an array sorted under insertions, and replacing it with a Fenwick tree over compressed values or a balanced search tree, with the cost of each.
    First step
    Count the work of the sorted list first: each insertion shifts on average half of the values already stored, and the list grows to 2 × 10⁵, so the shifts add up to about 10¹⁰ element moves. Then ask whether every value is known before the first question.
    Follow-ups

    From the lesson First, last and count with bounds

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  4. Mid to senior

    The check that tells a good build from a bad one is flaky: on a good build it reports a failure 5 % of the time. Your binary search over 1,000 builds sometimes blames the wrong build. What goes wrong, how do you make the search reliable, and what does that cost in checks?

    What it tests
    Seeing how one wrong answer misleads a binary search for good, estimating the error rate with numbers, and making the checks reliable by repetition at a stated cost.
    First step
    Work out how likely a wrong turn is. The search makes 10 checks and about half of them land on good builds, so with a 5 % false failure on each, the chance that at least one misleads it is about 1 − 0.95⁵, roughly 23 %. Then ask which answers can be trusted as they are.
    Follow-ups

    From the lesson Binary search on a monotone predicate

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  5. Mid to senior

    You can test two builds at the same time, and a round takes four minutes whatever you test in it. How many rounds do you need to find the first crashing build among n builds, which builds do you test in each round, and what changes with k phones?

    What it tests
    Generalising binary search to a search with k probes a round, the counting argument behind the number of rounds, and choosing the split points.
    First step
    Ask what two answers can tell you. With checks at builds a < b, the first crash is at or before a, between a and b, or after b: three outcomes a round, because a fine build after a crashing one cannot happen. That suggests splitting the candidates into three equal parts.
    Follow-ups

    From the lesson Binary search on a monotone predicate

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  6. Fresher to mid

    A colleague binary searches the first day on which a share price closed above 500. It passes the tests but gives wrong days in production. Why, how would you catch this in tests, and what would you compute instead?

    What it tests
    Recognising a condition that is not monotone, knowing what binary search returns on one, designing a test that exposes it, and restoring the single flip with a running maximum.
    First step
    Ask whether "closed above 500" can be true on one day and false on a later one. A price can rise above 500 and fall back, so the condition can flip many times, and the search will stop on some day where it turns true.
    Follow-ups

    From the lesson Binary search on a monotone predicate

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  7. Fresher to mid

    A teammate's search in a rotated sorted array passes every sample but returns −1 for [10, 20, 30, 0] with target 0. How do you find the faulty line, fix it, and convince yourself that no similar slip is left?

    What it tests
    Debugging a branchy binary search from its smallest failing input, the two-slot window where lo equals mid, and exhaustive tests over every short rotation.
    First step
    Trace the failing call by hand and write down lo, mid and hi at every pass. It goes wrong at the pass where the window has two slots, so that lo equals mid: check what each comparison says about a half of one slot.
    Follow-ups

    From the lesson Rotated arrays and peaks

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  8. Mid to senior

    Your search in a rotated sorted array must now accept repeated values, and the interviewer asks you to keep O(log n). What do you answer, and how do you prove it?

    What it tests
    Recognising when equal values remove the information a comparison gives, an adversary argument for a lower bound, and stating a complexity honestly.
    First step
    Find two inputs that your comparisons cannot tell apart: [2, 2, 2, 0, 2] and [2, 0, 2, 2, 2] hold the same values at both ends and in the middle, yet the 0 lies on different sides. Then ask whether any method could tell them apart without reading more slots.
    Follow-ups

    From the lesson Rotated arrays and peaks

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  9. Mid to senior

    A service returns the signal strength of channel i, one call at a time, for 10⁹ channels, and allows 64 calls. Find a channel at least as strong as both neighbours and prove that your method always succeeds. What changes if you need the strongest channel?

    What it tests
    Binary search on data with no order, an invariant that guarantees a peak, counting calls against a budget, and knowing when no sublinear method exists.
    First step
    Show first that a peak always exists: in any stretch, a strongest channel is a peak unless something stronger sits just outside the stretch. Then read two neighbours in the middle and decide which half must still contain a peak.
    Follow-ups

    From the lesson Rotated arrays and peaks

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  10. Mid to senior

    Your Java solution for the slowest reading speed keeps the total hours in an int and passed every test. When the limit on h is raised from 10⁹ to 2 × 10⁹, a test with 100,000 chapters of 10⁹ pages gets speed 1. Explain the failure, and why the old limits hid it.

    What it tests
    Reasoning about integer overflow with the real magnitudes, knowing which speeds a binary search actually checks, and fixing the type rather than the bounds.
    First step
    Work out the largest total the check could form: at speed 1 it is 10⁵ × 10⁹ = 10¹⁴ hours, far past 2,147,483,647. Then ask which speeds the search really checks, and how many hours the slowest of them can need.
    Follow-ups

    From the lesson Search on the answer: capacity and speed

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  11. Fresher to mid

    For the slowest reading speed, a teammate searches the speeds from 0 to 10⁹. What can go wrong at each end? Give tight bounds with a reason for each, and say how many checks they save for 10⁵ chapters of 10⁹ pages each with h = 2 × 10⁵.

    What it tests
    Choosing bounds that provably contain the answer, keeping a zero divisor out of the check, and judging honestly how much tight bounds save.
    First step
    Test each end against the promises of the search: the upper end must surely fit, and no speed below the lower end may fit. Then ask what a speed of 0 does to the check.
    Follow-ups

    From the lesson Search on the answer: capacity and speed

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  12. Mid to senior

    Change one rule of the reading-speed problem at a time. An hour may continue with the next chapter. Each chapter may be read at its own speed, and you minimise the fastest one. Or h becomes a number of days of at most 8 hours, and a chapter may continue the next day. Which changes still need a binary search?

    What it tests
    Seeing when a formula replaces the search, when a change leaves the answer unchanged, and when the check changes but stays monotone.
    First step
    For each change, write the hours that one speed needs. If the total no longer depends on how pages fall into hours, a formula may answer directly; otherwise ask whether a faster speed can still never need more time.
    Follow-ups

    From the lesson Search on the answer: capacity and speed

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  13. Mid to senior

    To split an ordered list into the fewest contiguous groups whose sums are each at most S, you fill each group as far as it goes. Prove that this uses the fewest groups, then show where the proof breaks if items may be negative.

    What it tests
    Writing a greedy-stays-ahead proof by induction, naming the assumption it rests on, and finding a counterexample when that assumption fails.
    First step
    Compare the greedy with any valid split group by group, and claim that after j groups the greedy has covered at least as many items. Then find the step that relies on a part of a valid group never summing to more than the group.
    Follow-ups

    From the lesson Minimise the maximum: split into k groups

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  14. Senior to staff

    The study group may now hand out chapters in any order: each student gets any set of chapters, and the most pages anyone reads should be as small as possible. Does the binary search still work? What would you do for 20 chapters, and for 10⁵?

    What it tests
    Seeing that dropping the order turns the task into scheduling on identical machines, which is NP-hard, and choosing an exact method for small inputs and a heuristic with a guarantee for large ones.
    First step
    Test the old proof on the new problem: greedy filling compared groups of one fixed order, and now there is none. Then look at two students: sharing the chapters into two equal halves is the partition problem.
    Follow-ups

    From the lesson Minimise the maximum: split into k groups

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  15. Mid to senior

    An O(n log S) binary search and an O(k × n²) dynamic programme both solve the ordered split into k groups. When would you choose the DP, how do you use each to test the other, and at what sizes does each stop being practical?

    What it tests
    Comparing two correct methods by cost and by the assumptions each needs, and using one as an independent judge for the other.
    First step
    Put numbers on both costs: for n = 10⁵ and k = 100 the search makes about 47 checks of 10⁵ steps, the DP about 5 × 10¹¹ steps. Then list what each method assumes about the cost of a group.
    Follow-ups

    From the lesson Minimise the maximum: split into k groups

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  16. Mid to senior

    A grid with sorted rows and sorted columns has 20 rows and 10⁶ columns, and your staircase search is too slow for 10⁵ queries. Explain why, and choose a better search, with read counts for both.

    What it tests
    Costing a search by the shape of the grid rather than by habit, comparing R + C with R log C, and knowing when a grid is one sorted list.
    First step
    Count the reads before changing code. The staircase may cross every column, up to R + C − 1 = 1,000,019 reads per query, so 10⁵ queries can need about 10¹¹ reads. Then count what a binary search of each of the 20 rows costs.
    Follow-ups

    From the lesson Sorted matrices: staircase and value search

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  17. Mid to senior

    Your value search for the k-th cheapest combo returns 5 for mains [3, 5, 9], drinks [1, 4, 6, 10] and k = 1, though no combo costs 5. Find the bug, fix it, and prove that the fixed search always returns a price some combo has.

    What it tests
    Lower bounds over values, why stopping when the count equals k is wrong, and a short proof that the answer is a price that exists.
    First step
    Write down the count for each candidate price: one combo costs at most 4, and still one costs at most 5. Several prices can have a count of exactly k, and only the smallest of them is the answer. Then look for the line that returns early.
    Follow-ups

    From the lesson Sorted matrices: staircase and value search

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  18. Mid to senior

    A Java solution for the k-th cheapest combo of two sorted menus of 50,000 prices each passes every small test, but for k = 2,400,000,000 it returns the dearest combo. What is wrong, how do you show it, and what else would you check?

    What it tests
    Spotting a 32-bit count in a search over values, reproducing an overflow with a constructed input, and checking every quantity that grows with the size of the grid.
    First step
    Work out the largest value each variable can hold: the count reaches 50,000 × 50,000 = 2.5 × 10⁹, beyond the 2,147,483,647 of an int. Then build an input whose answer you know, such as every main priced 1, and compare.
    Follow-ups

    From the lesson Sorted matrices: staircase and value search

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  19. Fresher to mid

    To place k chargers at given markers with every gap at least d, you take the leftmost site and then each next site at least d further on. Prove that this places the most chargers possible, and explain why the sites must be sorted first.

    What it tests
    A greedy-stays-ahead proof by induction, and seeing which step of it needs the sites in highway order.
    First step
    Compare the greedy's chargers with any valid placement, both in highway order, and claim that the greedy's i-th charger is never to the right of the other's i-th charger. Prove it for the first charger, then for each next one.
    Follow-ups

    From the lesson Maximise the minimum distance

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  20. Mid to senior

    The highway becomes a ring road of length L: markers run from 0 to L − 1, and the gap from the last charger back to the first wraps round. How do you find the widest smallest gap for k chargers, and what does it cost for n = 10⁵ sites?

    What it tests
    Adapting a greedy check to a cycle, choosing starting points without losing the best answer, and estimating the cost with numbers.
    First step
    On a ring no site is first, so the walk needs a starting charger. Fix the start at one site, walk greedily, and check the gap from the last charger back round to the start; then ask how many starts must be tried, and how fast each walk can be.
    Follow-ups

    From the lesson Maximise the minimum distance

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  21. Fresher to mid

    Your search for the widest gap passes the samples but hangs on a hidden test with two chargers. After a quick fix it returns 93 instead of 92 on another test. Explain both bugs from the loop's invariant, and write the loop so that neither can happen.

    What it tests
    Searching for a last true value, the rounding of the midpoint, what lo and hi mean when the loop ends, and choosing tests at the ends of the range.
    First step
    Write down what lo and hi promise and how each branch moves them. With lo = mid and the midpoint rounded down, try the state hi = lo + 1. Then check what the loop returns when the answer is the top of its range.
    Follow-ups

    From the lesson Maximise the minimum distance

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  22. Mid to senior

    You find the median of two sorted arrays by binary searching where to cut the shorter one. Prove that the cut your search returns splits all the values into a correct lower and upper half, and explain how you handle a cut at either end of an array.

    What it tests
    Turning a search into a proof: defining a correct cut, showing that the question flips once, and handling the ends of both arrays without special cases.
    First step
    Say what a correct cut means before any code: the part before the two cuts holds exactly half of the values, and every value in it is at most every value after the cuts. Then check which of those inequalities each comparison of your loop establishes, and which one comes from an earlier answer.
    Follow-ups

    From the lesson Partition search: median of two sorted arrays

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  23. Mid to senior

    Two services each hold a sorted list of up to 10⁹ numbers, readable one at a time over the network, and you may make at most 100 requests. How do you find the median of both lists, and how many requests does your method need in the worst case?

    What it tests
    Turning an O(log n) bound into a request count, choosing a loop that reads fewer values per pass, and checking the count by measurement.
    First step
    Price the merge first: about (m + n) / 2 requests, a billion here. Then count the requests one pass of a binary search over the cut needs, and multiply by the number of passes for 10⁹ values.
    Follow-ups

    From the lesson Partition search: median of two sorted arrays

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  24. Fresher to mid

    A Java median of two sorted int arrays passes every test with small values, but returns −97,483,648 for [2000000000] and [2100000000], and 4 for [3] and [6]. Explain both failures and fix them.

    What it tests
    Integer overflow and integer division in the final mean, choosing types for the sum of two values, and tests at the limits of a type.
    First step
    Look at the last line, the mean of the two middle values. Add 2,000,000,000 and 2,100,000,000 by hand and compare the sum with 2,147,483,647, then ask what int division does with 9 / 2.
    Follow-ups

    From the lesson Partition search: median of two sorted arrays

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

All Coding Interview Patterns interview questions · The Coding Interview Patterns track