Linear search checks the elements one by one from the start until it finds the target. Binary search uses the fact that the array is sorted: it looks at the middle element, and if that is too small it throws away the whole left half, if too big the right half, and repeats on what is left. This page runs both on the same sorted array at the same time, so you can see the difference in steps directly.
Binary search shows its lo, mid and hi pointers and greys out the half it has ruled out. Try a target near the end of a 100-element array: linear search needs close to 100 steps, binary search at most 7. Try a missing target to see how each one decides the value is not there.
How to use the Binary Search vs Linear Search tool
- Choose the array size and type a target value, or press Random target or Missing target.
- Press Search. Both searches start together.
- Watch the orange cell each search is checking, binary search’s lo, mid and hi labels, and the greyed-out elements each one has ruled out.
- Compare the step counters, and use Step and Back to follow the binary search decisions.
Why use ToolOrca Binary Search vs Linear Search
- Linear and binary search side by side on the same data
- lo, mid and hi pointers for binary search
- Ruled-out elements greyed out
- Step counters for both searches
- Targets that exist and targets that do not
- Pseudocode and code in C++, Java, Python and JavaScript
How binary search works
Start with lo = 0 and hi = n − 1. While lo ≤ hi, compute mid = (lo + hi) / 2 (rounded down). If a[mid] equals the target, you are done. If a[mid] is smaller, the target can only be to the right, so set lo = mid + 1; otherwise set hi = mid − 1. If lo passes hi, the target is not in the array.
Every step halves the remaining range, so binary search needs at most ⌊log₂ n⌋ + 1 steps: 7 for 100 elements, 20 for a million and 30 for a billion. In languages with fixed-size integers, write mid = lo + (hi − lo) / 2 to avoid overflow when lo + hi is very large.
Linear search vs binary search
Linear search works on any array, sorted or not, and is O(n): on average it checks half the elements. Binary search is O(log n) but needs the array to be sorted (and random access, so it does not work on a linked list). Sorting first costs O(n log n), so binary search pays off when you search the same data many times.
When to use each search
Use linear search for small arrays, unsorted data or a single search. Use binary search for repeated lookups in sorted arrays, and its variants to find the first or last occurrence, the insertion point (bisect in Python, lower_bound in C++) or the answer to “smallest x that satisfies a condition” problems. Hash tables give O(1) average lookups but lose the ordering.
Every visualizer on this site runs in your browser with the same controls: Play, Pause, Step forward, Step back and a speed slider. You can also drag the position slider to jump to any step, or focus the drawing and use the Space bar and arrow keys.
Frequently asked questions
What is the time complexity of binary search?
O(log n). Each comparison halves the search range, so a sorted array of 1,000,000 elements needs at most 20 comparisons.
Why does binary search need a sorted array?
It decides which half to discard by comparing the target with the middle element. That only works if everything left of the middle is smaller and everything right of it is larger.
When is linear search better than binary search?
When the data is unsorted, very small, stored in a linked list, or searched only once, so sorting it first would cost more than it saves.
How many steps does binary search take for 100 elements?
At most 7, because 2⁷ = 128 is the first power of two above 100.
Is binary search built into programming languages?
Yes: bisect in Python, Arrays.binarySearch and Collections.binarySearch in Java, std::binary_search and std::lower_bound in C++.