Implementation of a faster linear search, by sparing a single comparison.

gistfile1.cpp

#include<iostream>
#include<vector>
using namespace std;

int main()
{
  int sought = 4e8;

  vector<int> vec;
  for(size_t i = 0; i < sought + 20; i++)
    vec.push_back(i);

  size_t i = 0;

  // first: 3.5s
  for(;i < vec.size(); i++)
    if(vec[i] == sought) break;

  // second: 3.8s
  while(true) {
    if(vec[i] == sought) {
      break;
    } else {
      i++;

      if(i >= vec.size()) {
        break;
      }
    }
  }

  // 3.1s
  i = 0;
  vec.push_back(sought);

  while(true) {
    if(vec[i] == sought) {
      if (i < vec.size()) break; // success
      else if(i == vec.size()) break; // not success
    } else {
      i++;
    }
  }

  return 0;
}