parikshan

search-insert-position

Difficulty: Easy  ·  Topic: Binary Search  ·  Practice it on parikshan: /practice/search-insert-position/start

The story

Robinhood maintains an order book where buy orders sit sorted by price-ascending. When a market sell-order arrives at price P, the matching engine has to find the index of the first buy-order whose price is at least P so it can match from there. With 30 million resting orders, a linear scan is unthinkable. The matching engine has microseconds, not milliseconds.

That position is the insertion index: where P would slot in if you were inserting it into the sorted book. search-insert-position is the canonical formulation of "find the lower bound". Once you internalise it, you stop solving binary search problems one at a time and start writing the same five lines.

What's actually being asked

Given a sorted array of distinct integers nums and an integer target, return the index where target is found. If it is not present, return the index where it would be inserted to keep the array sorted.

Equivalently: return the smallest index i such that nums[i] >= target, or n if no such index exists.

You must run in O(log n).

The naive approach

Walk the array left to right; return the first index whose value is at least the target, otherwise return n. O(n). At 1,000,000 elements that is 1,000,000 comparisons per query. Datadog ingests millions of points per second; this scan will choke a Datadog histogram lookup the same way it chokes a Robinhood match.

The key insight

This is the canonical Binary Search variant called the lower bound. The predicate nums[mid] >= target is monotone: False on the left of the answer, True on the answer and everything to its right. You are not searching for the target; you are searching for the boundary of that predicate.

A single template handles three different questions at once: (1) target is present, (2) target is absent but fits in the middle, (3) target is larger than every element. Case 3 is where the half-open convention earns its keep: hi = n is a legal final answer.

Step-by-step approach

The half-open template. Memorise it; the rest of the binary-search cluster reuses it.

def search_insert(nums, target):
    lo, hi = 0, len(nums)              # hi exclusive: answer in [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] >= target:        # the monotone predicate
            hi = mid                   # mid could be the answer
        else:
            lo = mid + 1               # mid is definitely too small
    return lo                          # lo == hi: the boundary

The loop invariant in English: the answer lies in [lo, hi). Every iteration that invariant survives. When lo == hi, the half-open window has shrunk to nothing and lo is the single index it pointed at. Unlike the classic binary-search problem, there is no final equality check; lo itself is the answer for both hit and miss.

Worked example

nums = [1, 3, 5, 6]
target = 5
  • lo=0, hi=4. mid=2, nums[2]=5, 5≥5 → hi=2.
  • lo=0, hi=2. mid=1, nums[1]=3, 3<5 → lo=2.
  • lo=2, hi=2 → exit. Return 2. (Target found at index 2.)

Counter-case: target = 7. After two iterations the window collapses to lo=hi=4. Return 4 (insert at the end). The hi = n initial value is what made that legal.

Counter-case: target = 2. Window collapses to lo=hi=1. Return 1 (insert between 1 and 3).

Complexity

  • Time: O(log n).
  • Space: O(1).

For n = 1,000,000 the loop runs at most 20 times. The matching engine has its answer in tens of nanoseconds.

Common pitfalls

  1. Inclusive hi confusion. If you initialise hi = n - 1 you must use while lo <= hi and hi = mid - 1. Mixing conventions is the single most common reason agent-generated binary searches fail on length-zero or off-by-one cases.
  2. Returning -1 on miss. This is the binary-search reflex from the classic problem. Here a miss should return the insertion index, not a sentinel. Read the spec.
  3. Skipping the empty-array case. With n = 0, the half-open template returns 0 immediately (loop never runs). The inclusive template needs a separate guard. Another reason to prefer half-open.
  4. lo = mid infinite loop. When the window has length 2 and the predicate fails, you must advance lo past mid, not to it. The template uses lo = mid + 1 for exactly this reason.

Where this shows up in the enterprise

  • Robinhood / Coinbase matching engines: locating the first eligible counter-order at or above a price.
  • PostgreSQL b-tree index scans: the leaf-page lookup that finds the first tuple >= a search key is a lower bound.
  • Elasticsearch range queries: gte clauses on numeric fields land via lower-bound binary search over sorted doc values.
  • Datadog / Grafana time-series queries: finding the first sample at or after a query start timestamp.
  • Stripe invoice paging: cursor-based pagination uses lower bound on (created_at, id) to land on the first row of the next page.
  • TigerBeetle ledger lookups: the first transfer at or after an audit timestamp.
  • Apple Music / Spotify track libraries: scrolling to the first track in an alphabetised list.

The phrase to listen for in a feature spec is "the first row where ..." or "insertion index". Both are lower-bound binary searches.

Variants you'll see elsewhere

  • binary-search: same template; return -1 on miss instead of lo.
  • first-bad-version: same template against a predicate function rather than an array.
  • sqrt-x: same template against the integer answer space.
  • upper-bound: same template with the predicate nums[mid] > target instead of >=. Returns the index just after the last occurrence.
  • count-of-element = upper_bound(t) - lower_bound(t). Two calls of this template.

Three or four template-equivalent problems is the whole point: solve them once with the same scaffolding and you stop reinventing the loop.

How parikshan turns this into a learning loop

The trap with search-insert-position is that the four-line solution looks too short to need practice. It is not; the off-by-ones live in the simplicity. The parikshan flow is:

  1. Solve in practice mode with the AI off. Write the template by hand. Run it. Watch the public tests pass.
  2. The dynamic private tests generated per session will include the three edge cases that catch every wrong template: empty array, target smaller than everything, target larger than everything. Wrong templates pass two of three and fail the last silently.
  3. Turn AI on and ask it to Review your code. Note that the integrity score charges a small penalty; that cost is what makes you ask once and listen, instead of asking five times and skimming.
  4. If a private test fails and you believe your output is correct, the dispute flow sends the code to a human reviewer. The dispute system is rate-limited per session per hour so the channel stays usable for real disputes, not for re-rolls.

When you can produce this template in 30 seconds without re-reading the article, you have lower bound in your fingers and the rest of the Binary Search cluster collapses to one pattern.

In the AI-integrated workspace

Microsoft Copilot, Cursor, and Claude Code will write some flavour of binary search for almost every "find the first X where ..." spec they see. The bugs you have to spot are not in the algorithm; they are in the template inconsistency: the agent will sometimes return lo, sometimes lo + 1, sometimes hi, depending on which inclusive/exclusive convention it landed in mid-function. The code compiles. The tests on length 5 pass. The length-0 invocation in production returns -1 from a function spec'd to return an index in [0, n].

Your verification ritual on every agent-generated lower bound:

  1. Ask "is hi inclusive or exclusive?" The agent should answer in one word.
  2. Ask "what does the function return when target is larger than every element?" If the answer is "depends on the array" the template is wrong; the answer must be n (or len(nums)).
  3. Read the return statement. If it adds + 1 or subtracts, the template is mixed.

The candidates who run this checklist in ten seconds are the ones who ship correct binary search in seven languages despite each having different integer semantics. parikshan drills exactly that ritual.