title: Is Linear Binary Search an over optimization of standard Binary Search
body: <p>In understanding that Binary Search only works if the List you are searching is sorted, the assumption is that you maintain a sorted list if you are going to Search many times in an application. Searching linearly, 0(n), will always be faster than sorting and then searching, 0(nlog(n)) + log(n).</p>
  <p>However, in my research I found that, for small datasets, a linear search, 0(n) is faster than a logarithmic search 0(log(n)). It's recommended in a book I am reading that when searching a dataset with less than 20 items a linear search performs better than a binary search due to overhead in the binary implementation. (Programming and Problem Solving with C++ 6th Edition)</p>
  <p>A noticeable optimization to Merge Sort and Quick Sort implements a cutoff value which switches to Insertion sort when the list size becomes small enough... 15 or so items.</p>
  <p>Could something similar be done to Binary Search... Is there a noticeable difference in performance if you were to implement a cutoff to a linear search when the size of the list becomes small enough... 20 or so items...</p>
  <p>Binary Search Implementation:</p>
  <pre><code>int BinarySearch(std::vector&lt;int&gt;&amp; values, const int key) {
      int iLo = 0; int iHi = values.size() - 1;
      int iMid = (iHi + iLo) / 2;
  
      while(iLo &lt;= iHi) {
          if (key &lt; values[iMid])
              iHi = iMid - 1;
          else if (key &gt; values[iMid])
              iLo = iMid + 1;
          else
              return iMid;
  
          iMid = (iHi + iLo) / 2;
      }
      return -1;
  }
  </code></pre>
  <p>Binary Search with Linear Cutoff:</p>
  <pre><code>int LinearBinarySearch(std::vector&lt;int&gt;&amp; values, const int key) {
      int iLo = 0; int iHi = values.size() - 1;
      int iMid = (iHi + iLo) / 2;
  
      while (iLo &lt;= iHi) {
          if(iMid == key)
              return iMid;
  
          //Perform Linear Search When List Size is less than Cutoff
          if (iHi - iLo &lt; CUTOFF) {//Linear Search Performs better on List Size &lt; 20 or so...
          for (int i = iLo; i &lt;= iHi; i++) {
              if (values[i] == key)
                  return i;
          }
              return -1;
          }
  
          else if (key &lt; values[iMid])
              iHi = iMid - 1;
          else
              iLo = iMid + 1;
  
          iMid = (iHi + iLo) / 2;
      }
      return -1;
  }
  </code></pre>
  <p>I populated the Sorted List to be Searched:</p>
  <pre><code>for (int i = 0; i &lt; SIZE; i++) {
      values.push_back(i);
  }
  </code></pre>
  <p>Then timed the Search of 10 million items in the List with both Implementations of Binary Search and took the average runtime of each Implementation...</p>
  <p>The result on average was .000001 seconds per search for both Implementations showing that this cutoff only complicated the Binary Search and had no performance benefits...</p>
  <p>I would like to note that testing for equality on different data, such as strings, in the Linear Binary Search implementation may make a standard Binary Search faster, as the standard Binary Search does not test for equality. (This is an assumption that I have not tested)</p>
  <p>I guess the question still remains... Why implement a Linear Search over a Binary Search on small sorted data sets when Binary Search is not that complicated and is extremely scalable? Can Someone give an example...</p>