The Life Starter
Sign up
Grade 10 · lesson 4 of 4

Find the First Matching Sorted Position

Trace a lower-bound search with explicit half-open ranges.

Download the grade pack

Supplied materials

  • Paper and pencil; an adult may read aloud. No device, account or purchase is needed.

Learn the idea

A sorted list can contain duplicate values. An ordinary binary search may find any matching copy; a first-match requirement needs a precise variant. A lower-bound search finds the first position whose value is at least the target. It returns n if no such position exists. Check equality afterward to decide whether the target is present.

Use sorted list [2, 4, 4, 4, 7, 9]. Set lo = 0, hi = n, so the candidate range includes lo but excludes hi. While lo < hi: mid = floor((lo + hi)/2); if values[mid] < target, set lo = mid + 1; else set hi = mid. When the loop ends, lo is the insertion position. The supplied list stays sorted throughout.

  1. Trace target 4 with columns lo, hi, mid and inspected value.
  2. Keep the lower half including mid whenever its value is at least target.
  3. Stop when lo = hi, then check values[lo] only if lo < n.
  4. Trace absent target 5 and distinguish insertion position from a match.
Worked example

See the method in action

Target 4: (lo,hi)=(0,6), mid 3 value 4 → hi 3; mid 1 value 4 → hi 1; mid 0 value 2 → lo 1. Stop at position 1, first 4. Target 5 inspects 4,9,7 and stops at insertion position 4; value 7 is not equal, so report not found.

Your turn

Check your reasoning

Your answer is temporary and is not saved to an account. Download your current answer before leaving or reloading. Written work on paper or in another app stays in your own file.

For target 7 in the same list, what position does lower-bound search return?

Feedback appears here after you check. This is practice, not a graded school assessment.

See the answer and explanation

4

All earlier values are less than 7, and position 4 holds 7. The lower-bound result is position 4 and equality confirms a match.

Take it further

Change target to 10. Expected inspected values: 4, 9; return insertion position 6 = n and report not found without reading values[6].

Nothing here is saved to an account or sent to a teacher. The answer download includes your current choice and any checked feedback.

Check the subject sources

These LifeStarter passages, scenarios and exercises are authored for this Academy with AI assistance and review. External resources keep their publishers’ terms. A grade label suggests a starting level; it does not establish alignment with your school’s complete requirements.