GopherForgeA WORKBENCH FOR GO

Junior · Algorithms

Binary search as a boundary invariant

Find the first index whose value is at least a target.

Try explaining this aloud before opening the answer. State your assumptions and trace a boundary case.

ALGORITHM LAB · STEP THROUGH THE INVARIANT

[1, 3, 3, 8], target 3

STEP 1 / 5

Keep a half-open interval

Sorted input
10
31
32
83
lo / hi
00
41

Before lo is too small; hi is exclusive.

Computed traces for these inputs. Indexes identify cell positions; active cells are labeled as well as highlighted. Compare a boundary case using the scenario selector. No code is sent to a server.

EXAMPLE · FRAGMENT UNLESS A COMPLETE PROGRAM IS SHOWN

go
func LowerBound(xs []int, target int) int {
	lo, hi := 0, len(xs)
	for lo < hi {
		mid := lo + (hi-lo)/2
		if xs[mid] < target {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return lo
}
Reveal a strong answer

  1. Maintain a half-open search interval [lo, hi). All indexes before lo are known too small; every candidate answer remains inside the interval or at n. The sorted-input precondition is essential.

  2. Choose mid = lo + (hi-lo)/2. If xs[mid] < target, discard through mid; otherwise keep mid as a possible first answer by moving hi to mid. Each iteration strictly shrinks the interval.

  3. Returning lo handles duplicates and missing targets uniformly; lo == len(xs) means no qualifying element. Test empty input, all equal values, target outside the range and an exact duplicate boundary.

Common trap

Returning immediately on equality finds an arbitrary occurrence, not necessarily the first.

Complexity & use

O(log n) comparisons, O(1) extra storage. Useful for sorted event offsets and range boundaries.

Try it

For [1, 3, 3, 8] and target 3, trace every lo, hi and mid.

Worked solution

Start [0,4), mid2 qualifies → hi2. Mid1 qualifies → hi1. Mid0 is too small → lo1. Return1. For target9, return4. Use sort.Search or slices.BinarySearch when their contract matches.

Change the constraint

How would you find the last equal element without scanning all duplicates?

How did you do?

Self-assessment, not a compiler pass or interview score. Explain the reasoning unaided before marking understood.

Not marked. Progress stays on this browser, separate from course completion.

Primary references

Checked 2026-10-20. Use documentation for your pinned runtime, driver and tool version.