Algorithm playground
Binary search.
- Time (worst)
- O(log n)
- Space
- O(1)
One comparison. Half the possibilities. Watch the search space shrink.
Why use binary search?
We use binary search to find a target value in a sorted array efficiently. Instead of checking every element one by one, binary search checks the middle element and eliminates half of the remaining search space based on whether the target is smaller or larger. This reduces the time complexity from O(n) to O(log n), making it much faster for large datasets.
Customize array & target Try your own values or examples
Find 42
12 positions left to check · 0 comparisonsStart
Find 42 in a sorted array
The number inside a box is its value. The small number below is its position, called an index, starting at 0. Low and high show where to start and stop looking.
Sorted: smallest → largest. The outlined range contains the positions still possible.
Use Next for one action, or Play to watch. Drag the timeline to preview silently.
Voice narration is unavailable in this browser. You can still follow the on-screen explanations.
Follow the logic
Pythondef binary_search(a, target): low, high = 0, len(a) - 1 while low <= high: mid = low + (high - low) // 2 if a[mid] == target: return mid if a[mid] < target: low = mid + 1 else: high = mid - 1 return -1Keep this invariant in mind
If the target exists, it is always between low and high, inclusive.
Use Next step to go at your own pace. Try a missing target to see why the loop stops.
n is the number of items. Best-case time: O(1). Requires ascending sorted input. With duplicates, this version returns a matching index, not necessarily the first. Space complexity refers to the algorithm; playback stores extra snapshots for rewinding.

