Pattern visualizer
Halve the search space
Because the array is sorted, comparing the target to just one middle element tells you conclusively which half it could still be in — everything on the other side is guaranteed too small or too large, so it can be thrown away without ever being examined. Repeating that single trick shrinks the search space in half every time, so finding a value among n cells takes only about log2(n) probes. Reach for it whenever the data is sorted (or monotonic) and you need a fast lookup or boundary. Animated on: Find 23 in the sorted array [4, 9, 15, 23, 28, 37, 50].
Binary Search
step 1 / 11
4
[0]9
[1]15
[2]23
[3]28
[4]37
[5]50
[6]line 1
Sorted array, target 23. Sorted order is the superpower: one look at the middle tells us which half can be thrown away.
Pseudocode
1FUNCTION lowerBoundSearch(arr, target):2 lo = 0, hi = the length of arr - 13 WHILE lo < hi:4 mid = (lo + hi) / 2, rounded down5 IF arr[mid] < target: lo = mid + 16 ELSE: hi = mid7 END WHILE8 RETURN lo if arr[lo] === target, otherwise -19END FUNCTION
← / → step · space play · Home restart