A linear search works by looking at each element in a list
of data until it either finds the target or reaches the end. This results in
O(n) performance on a given list. A binary search comes with the prerequisite
that the data must be sorted. We can leverage this information to decrease the
number of items we need to look at to find our target. We know that if we look
at a random item in the data (let's say the middle item) and that item is
greater than our target, then all items to the right of that item will also be
greater than our target. This means that we only need to look at the left part
of the data. Basically, each time we search for the target and miss, we can
eliminate half of the remaining items. This gives us a nice O(log n) time
complexity.
Just remember that sorting data, even with the most
efficient algorithm, will always be slower than a linear search (the fastest
sorting algorithms are O(n * log n)). So you should never sort data just to
perform a single binary search later on. But if you will be performing many
searches (say at least O(log n) searches), it may be worthwhile to sort the
data so that you can perform binary searches. You might also consider other
data structures such as a hash table in such situations.
Image Source : https://en.wikipedia.org/wiki/Binary_search_algorithm
Example : Array is best example of linear search and tree
