Skip to content
All apps

Binary versus linear search

About this app

Run both searches on the same sorted array and compare step counts. See how halving the search space changes growth from linear to logarithmic.

Why halving is so fast

Linear search checks one element after another from the left and needs n comparisons in the worst case. Binary search requires a sorted array: it compares the target with the middle element and discards the left or the right half depending on the result. Every comparison halves the search range, so at most about log₂(n) + 1 comparisons are needed. With 128 elements that is 8 instead of up to 128, with a million about 20 instead of a million.

What the app shows

Two cards side by side: on the left the binary search, which halves the range with the middle bar it is currently comparing, and on the right the linear search, which checks every element from the left. The target value sits above both. A values panel shows n, log₂(n), the steps of both methods and the factor by which linear search needs more steps, all live.

Try it yourself

Choose an array size of 8, 16, 32, 64 or 128, set a random target or click one, and start both searches at once or step by step at an adjustable speed. Put the target at the far right to see the worst case of linear search, then double n: binary search needs only one more step.

Frequently asked questions

How does binary search work?
In a sorted array the middle element is compared with the target. If the target is smaller, the search continues in the left half; if it is larger, in the right half. This repeats until the target is found or the range is empty.
What is the time complexity of binary search?
O(log n). Because the range halves with every comparison, n elements need at most about log₂(n) + 1 comparisons. Linear search needs O(n), so n comparisons in the worst case.
When can't you use binary search?
When the data is not sorted or there is no fast access to an arbitrary element, as in a linked list. For a single search in unsorted data, linear search is cheaper than sorting first.
What does the binary search app show?
Binary and linear search run side by side on the same array of 8 to 128 elements. Step counters, log₂(n) and the factor between the two methods are shown live, and you set the target and the speed yourself.

Subject: Computer science

More from Computer science

A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps