title: Linear search vs binary search real time performance in C++
body: <p>Getting totally unexpected results while comparing binary search vs linear search's real time performance in C++ using the code below  -</p>
  <pre><code>typedef std::chrono::microseconds us;
  
  int linear_search(uint64_t* val, int s, int e, uint64_t k) {
      while (s &lt; e) {
        if (!less&lt;uint64_t&gt;()(val[s], k)) {
          break;
        }
        ++s;
      }
      return {s};
  }
  
  int binary_search(uint64_t* val, int s, int e, uint64_t k) {
      while (s != e) {
        const int mid = (s + e) &gt;&gt; 1;
        if (less&lt;uint64_t&gt;()(val[mid], k)) {
          s = mid + 1;
        } else {
          e = mid;
        }
      }
      return {s};
  }
  
  
  int main() {
  
      // Preparing data
      int iter = 1000000;
      int m = 1000;
      uint64_t val[m];
      for(int i = 0; i &lt; m;i++) {
          val[i] = rand();
      }
      sort(val, val + m);
      uint64_t key = rand();
  
      // Linear search time computation
      auto start = std::chrono::system_clock::now();
      for (int i = 0; i &lt; iter; i++) {
          linear_search(val, 0, m - 1, key);
      }
      auto end = std::chrono::system_clock::now();
      auto elapsed_us = std::chrono::duration_cast&lt;us&gt;(end - start);
      std::cout &lt;&lt; &quot;Linear search: &quot; &lt;&lt; m &lt;&lt; &quot; values &quot;
                &lt;&lt; elapsed_us.count() &lt;&lt; &quot;us\n&quot;;
  
      // Binary search time computation
      start = std::chrono::system_clock::now();
      for (int i = 0; i &lt; iter; i++) {
          binary_search(val, 0, m - 1, key);
      }
      end = std::chrono::system_clock::now();
      elapsed_us = std::chrono::duration_cast&lt;us&gt;(end - start);
      std::cout &lt;&lt; &quot;Binary search: &quot; &lt;&lt; m &lt;&lt;&quot; values &quot;
                &lt;&lt; elapsed_us.count() &lt;&lt; &quot;us\n&quot;;
  }
  
  </code></pre>
  <p>Compiling without optimisation, getting following output -</p>
  <pre><code>Linear search: 1000 values 1848621us
  Binary search: 1000 values 24975us
  </code></pre>
  <p>When compiled with -O3 optimisation, getting this output -</p>
  <pre><code>Linear search: 1000 values 0us
  Binary search: 1000 values 13424us
  </code></pre>
  <p>I understand that for small array size, binary search may be expensive than linear but can't understand reason for difference of this magnitude by adding -O3</p>