Binary Search Interactive Laboratory

Binary search needs the values in sorted order. The page sorts its randomly generated unique values before searching. Consider this illustrative sorted nine element array and target twenty eight. Low begins at index zero and high at eight. Taking the floor of their average selects index four, whose value is twenty. Because twenty is smaller than the target, every value through index four can be discarded. Sorted order makes that deduction valid. The surviving indices are five through eight. Their midpoint is floor of thirteen divided by two, which is six. The value at index six is twenty eight, so the search stops after two comparisons. Seven would be the count for a linear search starting at the left. The animation also shows initialization and bound updates as separate frames. Those frames are not additional midpoint comparisons. An unsuccessful search ends when low crosses high. The page can generate a missing target above the largest value, allowing you to inspect that boundary. Its displayed bound for nine values is ceiling of log base two of ten, which is four comparisons. Preset names still need to be checked against the actual trace: with sixteen values, Best Mid selects index eight, but the first lower midpoint is index seven. That preset therefore takes four comparisons in this implementation, not one.