В день 0 я начал с простого алгоритма линейного поиска, который будет искать нужные данные в массиве.

На самом деле я рассмотрел три способа реализации алгоритма линейного поиска, два из них — итеративный, а один — рекурсивный.

Algorithm 0.1 
Method linear_search(arr, n, data)
for(i in range in range of [0,n) )
    if(arr[i] is equal to x)
        return index i
else return -1 that means element not found.

Здесь в 0.1 нет необходимости перебирать весь массив, сразу возвращается индекс, по которому будут найдены данные, без перебора всего цикла.

Algorithm 0.2
Method sentinal_linear_search(arr, n, data)
save arr[n - 1] into last
store data into arr[n-1]
set i = 0
while arr[i] not equal to data
    increment i
now restore arr[n-1] from last
if i<n-1 or arr[n-1] is equal to x
    return i
else return -1 which means element not found.

sentinal — лучший алгоритм линейного поиска, потому что в нем выполняется только одна проверка только для проверки того, присутствуют ли искомые данные в массиве или нет, вместо двух повторных проверок в 0.1. Проверка индекса за пределами границы реализуется только один раз, что является основным преимуществом версии 0.2.

Algorithm 0.3
Method recursive_linear _search(arr, n, i, data)
here i is the preesent index .
base case : if i > n-1 return  -1 (element not found)
if arr[i] is equal to data
   return i
else
   return recursive_linear_search(arr, n, i+1, data)

Теперь часть реализации:

Я скоро отредактирую сообщение и добавлю объяснение временной сложности для вышеизложенного. Спасибо !