What is the difference between Linear search and Binary search?

Question

What is the difference between Linear search and Binary search?

Answer 1

A linear search looks down a list, one item at a time, without jumping. In complexity terms this is an O(n) search - the time taken to search the list gets bigger at the same rate as the list does.

A binary search is when you start with the middle of a sorted list, and see whether that's greater than or less than the value you're looking for, which determines whether the value is in the first or second half of the list. Jump to the half way through the sublist, and compare again etc. This is pretty much how humans typically look up a word in a dictionary (although we use better heuristics, obviously - if you're looking for "cat" you don't start off at "M"). In complexity terms this is an O(log n) search - the number of search operations grows more slowly than the list does, because you're halving the "search space" with each operation.

As an example, suppose you were looking for U in an A-Z list of letters (index 0-25; we're looking for the value at index 20).

A linear search would ask:

list[0] == 'U'? No.
list[1] == 'U'? No.
list[2] == 'U'? No.
list[3] == 'U'? No.
list[4] == 'U'? No.
list[5] == 'U'? No.
... list[20] == 'U'? Yes. Finished.

The binary search would ask:

Compare list[12] ('M') with 'U': Smaller, look further on. (Range=13-25)
Compare list[19] ('T') with 'U': Smaller, look further on. (Range=20-25)
Compare list[22] ('W') with 'U': Bigger, look earlier. (Range=20-21)
Compare list[20] ('U') with 'U': Found it! Finished.

Comparing the two:

• Binary search requires the input data to be sorted; linear search doesn't
• Binary search requires an ordering comparison; linear search only requires equality comparisons
• Binary search has complexity O(log n); linear search has complexity O(n) as discussed earlier
• Binary search requires random access to the data; linear search only requires sequential access (this can be very important - it means a linear search can stream data of arbitrary size)