I was experimenting with some known algorithm which aims to reduce the number of comparisons in an operation of finding element in an unsorted array. The algorithm uses sentinel which is added to the back of the array, which allows to write a loop where we use only one comparison, instead of two. It's important to note that the overall Big O computational complexity is not changed, it is still O(n). However, when looking at the number of comparisons, the standard finding algorithm is so to say O(2n) while the sentinel algorithm is O(n).

Standard find algorithm from the c++ library works like this:

```
template<class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value)
{
    for (; first != last; ++first) {
        if (*first == value) {
            return first;
        }
    }
    return last;
}

```

We can see two comparisons there and one increment. 

In the algorithm with sentinel the loop looks like this:

```
while (a[i] != key)
      ++i;

```

There is only one comparison and one increment.

I made some experiments and measured time, but on every computer the results were different. Unfortunately I didn't have access to any serious machine, I only had my laptop with VirtualBox there with Ubuntu, under which I compiled and run the code. I had a problem with the amount of memory. I tried using online compilers like Wandbox and Ideone but the time limits and memory limits didn't allow me to make reliable experiments. But every time I run my code, changing the number of elements in my vector or changing the number of execution of my test, I saw different results. Sometimes the times were comparable, sometimes std::find was significantly faster, sometimes significantly faster was the sentinel algorithm. 

I was surprised because the logic says that the sentinel version indeed should work faster and every time. Do you have any explanation for this? Do you have any experience with this kind of algorithm? Is it worht the effort to even try to use it in production code when performance is crucial and when the array cannot be sorted (and any other mechanism to solve this problem, like hashmap, indexing etc., cannot be used)?

Here's my code of testing this. It's not beautiful, in fact it is ugly, but the beauty wasn't my goal here. Maybe something is wrong with my code?

```
#include <iostream>
#include <algorithm>
#include <chrono>
#include <vector>
using namespace std::chrono;
using namespace std;

const unsigned long long N = 300000000U;

static void find_with_sentinel()
{
   vector<char> a(N);
   char key = 1;
   a[N - 2] = key; // make sure the searched element is in the array at the last but one index

   unsigned long long high = N - 1;
   auto tmp = a[high];

   // put a sentinel at the end of the array
   a[high] = key;

   unsigned long long i = 0;
   while (a[i] != key)
      ++i;

   // restore original value
   a[high] = tmp;

   if (i == high && key != tmp)
      cout << "find with sentinel, not found" << endl;
   else
      cout << "find with sentinel, found" << endl;
}

static void find_with_std_find()
{
   vector<char> a(N);
   int key = 1;
   a[N - 2] = key; // make sure the searched element is in the array at the last but one index

   auto pos = find(begin(a), end(a), key);
   if (pos != end(a))
      cout << "find with std::find, found" << endl;
   else
      cout << "find with sentinel, not found" << endl;
}

int main()
{
   const int times = 10;
   high_resolution_clock::time_point t1 = high_resolution_clock::now();
   for (auto i = 0; i < times; ++i)
      find_with_std_find();
   high_resolution_clock::time_point t2 = high_resolution_clock::now();
   auto duration = duration_cast<milliseconds>(t2 - t1).count();
   cout << "std::find time = " << duration << endl;

   t1 = high_resolution_clock::now();
   for (auto i = 0; i < times; ++i)
      find_with_sentinel();
   t2 = high_resolution_clock::now();
   duration = duration_cast<milliseconds>(t2 - t1).count();
   cout << "sentinel time = " << duration << endl;
}

```