Интересная оптимизация линейного поиска

Посмотрим сегодня на всеми известный классический алгоритм линейного поиска:

public static int linearSearch(int[] a, int x) {
 
 int length = a.length;
 
 for (int i = 0; i < length; ++i) {
  if (a[i] == x) {
   return i;
  }
 }
 
 return -1;
}

Вроде все с ним хорошо, но данный алгоритм можно сделать еще эффективнее. Если внимательно присмотреться, то на каждом витке цикла мы делаем две проверки: не закончился ли наш массив и непосредственно само сравнение с искомым элементом.

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

Далее запускаем цикл и проверяем только на совпадение с образцом. Цикл в любом случае закончится. В конце вернем последний элемент на место и сделаем простую проверку. Если мы не дошли до конца или последний элемент равен искомому, то наш поиск увенчался успехом.

public static int sentinelLinearSearch(int[] a, int x) {
 
 int lastIndex = a.length - 1;
 int last = a[lastIndex];
 
 a[lastIndex] = x;
 
 int i = 0;
 while (a[i] != x) {
  ++i;
 }
 
 a[lastIndex] = last;
 
 if (i < lastIndex || a[lastIndex] == x) {
  return i;
 } 
 
 return -1;
}