title: Is "==" in sorted array not faster than unsorted array?
body: <p><em>Note: the alleged duplicate question is, I think, mostly related to "&lt;" and ">" comparison, but not "==" comparison and hence does not answer my question about performance of the "==" operator.</em></p>
  
  <p>For a long time, I have believed that "processing" a sorted array should be faster than an unsorted array. At first, I thought using "==" in a sorted array should be faster than in unsorted array because - I guess - of how branch prediction works:</p>
  
  <p>UNSORTEDARRAY:</p>
  
  <pre><code>5 == 100 F
  43 == 100 F
  100 == 100 T
  250 == 100 F
  6 == 100 F
  (other elements to check)
  </code></pre>
  
  <p>SORTEDARRAY:</p>
  
  <pre><code>5 == 100 F
  6 == 100 F
  43 == 100 F
  100 == 100 T
  (no need to check other elements, so all are F)
  </code></pre>
  
  <p>so I guess SORTEDARRAY should be faster than UNSORTEDARRAY, but today I used the code to generate 2 arrays in a header to test, and branch prediction seemed not to work as I thought.</p>
  
  <p>I generated an unsorted array and a sorted array to test:</p>
  
  <pre><code>srand(time(NULL));
  int UNSORTEDARRAY[524288];
  int SORTEDARRAY[sizeof(UNSORTEDARRAY)/sizeof(int)];
  for(int i=0;i&lt;sizeof(SORTEDARRAY)/sizeof(int);i++){
      SORTEDARRAY[i]=UNSORTEDARRAY[i]=rand();
  }
  sort(SORTEDARRAY,SORTEDARRAY+sizeof(SORTEDARRAY)/sizeof(int));
  string u="const int UNSORTEDARRAY[]={";
  string s="const int SORTEDARRAY[]={";
  for(int i=0;i&lt;sizeof(UNSORTEDARRAY)/sizeof(int);i++){
      u+=to_string(UNSORTEDARRAY[i])+",";
      s+=to_string(SORTEDARRAY[i])+",";
  }
  u.erase(u.end()-1);
  s.erase(s.end()-1);
  u+="};\n";
  s+="};\n";
  ofstream out("number.h");
  string code=u+s;
  out &lt;&lt; code;
  out.close();
  </code></pre>
  
  <p>so to test, just count if the value is == RAND_MAX/2 like this:</p>
  
  <pre><code>#include "number.h"
  int main(){
  int count;
      clock_t start = clock();
      for(int i=0;i&lt;sizeof(SORTEDARRAY)/sizeof(int);i++){
          if(SORTEDARRAY[i]==RAND_MAX/2){
              count++;
          }
      }
      printf("%f\n",(float)(clock()-start)/CLOCKS_PER_SEC);
  }
  </code></pre>
  
  <p>run 3 times:</p>
  
  <p>UNSORTEDARRAY</p>
  
  <pre><code>0.005376
  0.005239
  0.005220
  </code></pre>
  
  <p>SORTEDARRAY</p>
  
  <pre><code>0.005334
  0.005120
  0.005223
  </code></pre>
  
  <p>it seems a small performance difference, so I didn't believe it and then tried to change "SORTEDARRAY[i]==RAND_MAX/2" to "SORTEDARRAY[i]>RAND_MAX/2" to see if it made a difference:</p>
  
  <p>UNSORTEDARRAY</p>
  
  <pre><code>0.008407
  0.008363
  0.008606
  </code></pre>
  
  <p>SORTEDARRAY</p>
  
  <pre><code>0.005306
  0.005227
  0.005146
  </code></pre>
  
  <p>this time there is a great difference.</p>
  
  <p>Is "==" in the sorted array not faster than an unsorted array? If yes, why is ">" in sorted array faster than an unsorted array but "==" is not?</p>