Binary Search Versus Linear Search

Binary Vs Linear Search

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.  

Consider the following table of Worst-case search values for different array sizes.  For an array of 10,000 elements, the worst case for linear search is 10,000 comparisons.  For the Binary search, it is only 14.  Quite a difference!  We will have to wait until the next lecture to see what the cost is for sorting the original array.  Remember that the Binary Search algorithm depends on the array already being sorted.  You need to understand the relative efficiencies of these two searching algorithms and now they work.  If you have an array that is not sorted, and you only need to search through it once, you may want to use a linear search, since you won’t have to sort it first.  If you have a sorted array, or have to search many times, using a Binary Search is the obvious choice.

What about if you have an unsorted array, and you need to do hundreds or thousands of searches in it?  Well, then you have a design decision to make.  It may be a significant cost to sort the array (see the next lesson), but you will, in the worst case, save thousands to millions of comparisons for your searches.  So what algorithm(s) you choose depends on what your program needs to do.  Learning how to choose means learning what algorithms you have available to you, how they work, and what each is good for.

Leave a Reply

Your email address will not be published. Required fields are marked *