Binary Search

Binary search is what sorting was for. Once the array is in order you never have to look at most of it. Keep a window that must contain the target if it is there at all, check the value in the middle, and throw away the half that cannot possibly hold it. One comparison, half the list gone.

Do that again and again and the window collapses fast. Every probe halves what is left, so a thousand items take about ten looks and a million take about twenty. That is O(log n), and next to linear search’s straight line it barely moves as the list grows. The catch is the one rule you cannot break: the data has to be sorted, because the whole trick rests on knowing which half to discard.

Watch the shaded band in the visualizer: that is the live window, and it shrinks by half on every step. Type a value into the search box to look for something specific, or leave it empty and let the Target menu pick one that is present or falls in a gap. Data switches between numbers and words, and New array deals a fresh sorted set.