Binary Search Vs Linear Search

A linear search is the basic and simple search algorithm. A linear search searches an element or value from an array till the desired element or value is not found and it searches in a sequence order. It compares the element with all the other elements given in the list and if the element is matched it returns the value index else it return -1. Linear Search is applied on the unsorted or unordered list when there are fewer elements in a list.binary-and-linear-search-animations

animation courtesy

Binary Search is applied on the sorted array or list. In binary search, we first compare the value with the elements in the middle position of the array. If the value is matched, then we return the value. If the value is less than the middle element, then it must lie in the lower half of the array and if it’s greater than the element then it must lie in the upper half of the array. We repeat this procedure on the lower (or upper) half of the array. Binary Search is useful when there are large numbers of elements in an array.

The Binary Search is much more efficient than the linear search, but we must pay initially to sort the array (you learn about sorting in the next lesson).  Once it is sorted, the best case performance is one comparison (the searched-for value is the mid-point value in the original array).  The worst-case, where the value is not in the array, is log2N, where N is the size of the array. The nomenclature log2 stands for the base 2 logarithm.  You don’t have to understand WHY this is the worst case for this algorithm. Section 11.1 in the book has a very terse explanation of how to calculate this, and if you are interested, you can look through it.  If not, just believe that it is until you go farther in studying computer science algorithms.  Calculating the efficiency of algorithms like this is a part of computer science all to itself.

Leave a Reply

Share This

Sharing is Caring

Share this post with your friends!