Implement Lower Bound

Binary search that keeps searching after it finds a match

time O(log n)space O(1)

Plain binary search stops the moment it hits the target, which is useless when the target repeats — you land on an arbitrary copy. A bound search never stops early: when mid qualifies it RECORDS mid as the best answer so far and then keeps searching the left half for an even earlier one. That single change turns binary search into 'first index satisfying a predicate'. Lower bound uses >= target, upper bound uses > target, and the two together bracket the whole run of equal values, so ub - lb counts occurrences without ever scanning them.

Details

Animated on: A = [1,3,5,5,5,8,9,11], target = 5 — find the first index with A[i] >= 5 (lower bound) and the first with A[i] > 5 (upper bound).

Problem:Implement Lower BoundEasy

Binary search that keeps searching after it finds a match

step 1 / 12

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Sorted array with 5 repeated. A plain binary search finds SOME 5 but can't say where the run starts or ends. Two bounds pin it down: lower bound = first index >= 5, upper bound = first index > 5.

Pseudocode

1FUNCTION BOUND(A, target)
2  low <- 0
3  high <- LENGTH(A) - 1
4  ans <- LENGTH(A)
5  WHILE low <= high
6    mid <- (low + high) / 2
7    IF A[mid] >= target
8      ans <- mid
9      high <- mid - 1
10    ELSE
11      low <- mid + 1
12  RETURN ans

← / → step · space play · Home restart

Every step in words

Show all 12 steps

Sorted array with 5 repeated. A plain binary search finds SOME 5 but can't say where the run starts or ends. Two bounds pin it down: lower bound = first index >= 5, upper bound = first index > 5.
First pass, the lower bound: find the first index whose value is >= 5. Search the whole array, and start ans at 8 (one past the end) so "no index qualifies" is already the answer if none ever does.
A[3]=5 is >= 5, so index 3 qualifies — but an EARLIER index might too. Record it (ans 8 -> 3) and keep hunting left: high = 2.
A[1]=3 is not >= 5. The array is sorted, so every index at or left of 1 fails too — discard that whole half: low = 2.
A[2]=5 is >= 5, so index 2 qualifies — but an EARLIER index might too. Record it (ans 3 -> 2) and keep hunting left: high = 1.
low (2) has passed high (1), so no unchecked index remains. Because every qualifying mid pushed the search further left, the recorded ans is the LEFTMOST one: A[2]=5 at index 2 is the lower bound of 5.
Second pass, the upper bound — identical code, the only change is testing > 5. Search the whole array, and start ans at 8 (one past the end) so "no index qualifies" is already the answer if none ever does.
A[3]=5 is not > 5. The array is sorted, so every index at or left of 3 fails too — discard that whole half: low = 4.
A[5]=8 is > 5, so index 5 qualifies — but an EARLIER index might too. Record it (ans 8 -> 5) and keep hunting left: high = 4.
A[4]=5 is not > 5. The array is sorted, so every index at or left of 4 fails too — discard that whole half: low = 5.
low (5) has passed high (4), so no unchecked index remains. Because every qualifying mid pushed the search further left, the recorded ans is the LEFTMOST one: A[5]=8 at index 5 is the upper bound of 5.
lb=2 and ub=5 bracket the half-open range [2, 5) — every copy of 5 and nothing else. Their difference 5 - 2 = 3 is the count of 5, in O(log n) instead of a scan.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Implement Lower Bound in the editor All Binary Search problems Back to roadmap