# Binary search visualised: O(log n) on sorted arrays

> Interactive binary search: halves the search range using the middle and shifts lo or hi. Requires a sorted array, runs in O(log n) with constant extra memory.

Address: https://marckimmel.de/en/informatik/suchalgorithmen/binaere-suche
Deutsche Fassung: https://marckimmel.de/informatik/suchalgorithmen/binaere-suche.md

Halves the search range each step by comparing the middle to the target.

Binary search relies on a sorted array and uses that order to halve the remaining range each step. It keeps two boundaries lo and hi and computes the middle mid. Then it compares a[mid] against the target: an equal value is the hit; a smaller a[mid] means the target can only be to the right, so lo is set to mid+1; a larger a[mid] sends the search left and hi becomes mid-1. As soon as lo > hi the range is empty and the value is not in the array. Halving the range every iteration means at most log2(n)+1 steps, giving a logarithmic runtime O(log n) in average and worst case; in the best case the very first mid is the hit (O(1)). Extra memory stays constant (O(1)). The requirement remains: the array must be sorted and allow random access. The visualizer therefore sorts the input automatically.

First choice once the data is sorted and random access is allowed, for example an array in memory or an indexed column in a database. The classic solution for fast lookups in large, mostly static data sets.

## Related

- [Search Algorithms](https://marckimmel.de/en/informatik/suchalgorithmen.md)