The Runtime Theory
easyleetcode#binary-search#boundary-search

Find the First Valid Position

Implement lower-bound binary search and explain the invariant that makes each discarded half impossible.

The Runtime Theory Team1 min read
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

innums=[1,3,5,6], target=5

out2

innums=[1,3,5,6], target=2

out-1

innums=[], target=4

out-1

Implement a search over a sorted integer array. Return the index of the target or -1 when it is absent. Then adapt your implementation to return the lower-bound insertion position and explain which comparison changes.

Acceptance criteria

  • Empty input and a one-element array behave correctly.
  • Duplicate values have a documented result policy.
  • The search range shrinks on every iteration.
  • Explain why the input must be sorted and why lo + (hi - lo) / 2 avoids a bounded-integer overflow.

Use the linked judge for the original challenge. Before submitting, trace the interval after each comparison on a target below the first element, between values, and above the last element.

More practice in this topic

easy · programming algorithmsImplement Binary Search

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save