Алгоритмы поиска по массиву.

Сегодня читаю книгу: Алгоритмы. Вводный курс. Автор: Томас Х.Кормен.

Книга ориентирована как раз на таких как я, который не имеют математического образования и рассказывают теорию алгоритмов на пальцах.

Во второй главе описывается некая функция: Linear-Search(), которая занимается поиском искомого значения в массиве.

Первая версия поиска по массиву: Linear Search

1. Установить значение answer равным Not-Found
2. Для каждого индекса i, пробегающего поочередно значения от 1 до n:
1.  Если A[i] = x, установить значение answer равным i.
3. В качестве выходного вернуть значение answer.

Как я это представляю в коде (язык C#):

int LinearSearch(int[] A, int x, int n)
{
    for (int i = 0; i < n; i++)
    {
        if (A[i] == x)
        {
            return A[i];
        }
    }
}

Данный метод-функция не идеальная, т.к. допускает ошибки. Сам автор пишет на псевдокоде(там алгоритм несколько иной) и утверждает, что эту функцию можно оптимизировать!

Вторая версия поиска по массиву: Sentinel-Linear-Search
Суть объяснить пока не могу, поэтому напишу код, который понял. Суть такая: выход за пределы цикла while не происходит, т.к. последний элемент A[n] == x! Якобы этот вариант поиска по массиву лучше обычного, т.к. производит меньше операций.

int SentinelLinearSearch(int[] A, int x, int n)
{
    int last = A[n];
    A[n] = x;
    int i = 0;
   
    while (A[i] != x)
    {
        i++;
    }

    A[n] = last;

    if (i < n || A[n] == x)
        return i;
    else
        return 0;
}

ИТОГО

Собственно почитал, подумал. Пришел к мысли, что способов поиска по массивам можно выдумать много и они будут для каждого языка оригинальными. Попробую в этом топике собирать способы поиска по массивам на разных языках.

Понять как подсчитывать расход времени на ту или иную операцию...