loading
loading
loading
Computer Science / Algorithms
Scan a list left to right, one element at a time, until the target turns up or the list runs out — no sorted-input requirement, unlike Binary Search.
Linear search checks every element in order, starting at index 0, comparing each one to the target until it finds a match or runs out of elements. It makes no assumption about the input's order — unlike Binary Search, which requires the array to be sorted before it can eliminate half the search space on every comparison. That lack of a precondition is linear search's whole advantage: it works on any sequence, sorted or not. The cost is that it may have to check every single element — O(n) in the worst case, versus Binary Search's O(log n) — so on a large, already-sorted dataset, Binary Search will almost always win. Press New List to generate a new random unsorted list and target and watch the scan repeat on a different case, including runs where the target isn't present at all.
Binary search's speed comes entirely from an assumption: everything below the midpoint is smaller and everything above is larger, so it can safely discard half the range on every comparison. Linear search makes no such assumption — it simply checks each element in turn — which is why it works on any order but can't skip anything.
On small lists, on data that isn't sorted and won't be searched more than once (sorting first would cost more than the search saves), or on data structures without random access — like a linked list — where binary search's O(log n) advantage doesn't apply anyway.
In the worst case — the target is the last element checked, or absent entirely — every one of the n elements gets exactly one comparison, and there's no assumption like sortedness to lean on to skip any of them.