Pattern visualizer
Lower Bound and Upper Bound
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. 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)..
Binary search that keeps searching after it finds a match
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.
1FUNCTION BOUND(A, target)2 low <- 03 high <- LENGTH(A) - 14 ans <- LENGTH(A)5 WHILE low <= high6 mid <- (low + high) / 27 IF A[mid] >= target8 ans <- mid9 high <- mid - 110 ELSE11 low <- mid + 112 RETURN ans
← / → step · space play · Home restart