Поиск элемента в массиве

Достаточно частая задача - это поиск элемента в массиве. Допустим у нас есть массив 1,5,8,10,16,20... 100 и нам нужно найти позицию элемента 10 в нем. Или вообще выяснить есть ли такой элемент в массиве. 

Существуют следующие алгоритмы решающие эту задачу:

• Линейный поиск  - О(n)
• Двоичный поиск  - O(log (N))
• Поиск прыжками - O(sqrt (N))
• Интерполяционный поиск - O(log log N)
• Экспоненциальный поиск - O(log (N))

Рассмотрим некоторые из них.

1. Линейный поиск

Самый простой, но и самый долгий алгоритм. Перебираем элементы массива и сравниваем с elementToSearch, который мы должны найти.

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

2. Двоичный поиск, итеративный подход

Для использования алгоритма, массив должен быть отсортирован. Идея метода состоит в том, что мы делим массив пополам, берем "средний элемент" с индексом middleIndex, и сравниваем с искомым. Если они равны, мы заканчиваем поиск. Если искомый элемент меньше "среднего элемента" мы отбрасываем правую часть массива, иначе - левую. После чего повторяем эти операции снова и снова, пока искомый элемент не будет найден, или пока новый отрезок не станет пустым. Если элемент не нашелся возвращаем значение -1.

public static int binarySearch(int[] array, int elementToSearch) {
        int firstIndex = 0;
        int lastIndex = array.length - 1;

        // условие прекращения (элемент не представлен)
        while (firstIndex <= lastIndex) {
            int middleIndex = (firstIndex + lastIndex) / 2;
            // если средний элемент - целевой элемент, вернуть его индекс
            if (array[middleIndex] == elementToSearch) {
                return middleIndex;
            }

            // если средний элемент меньше
            // направляем наш индекс в middle+1, убирая первую часть из рассмотрения
            else if (array[middleIndex] < elementToSearch) {
                firstIndex = middleIndex + 1;
            }
            // если средний элемент больше
            // направляем наш индекс в middle-1, убирая вторую часть из рассмотрения
            else if (array[middleIndex] > elementToSearch) {
                lastIndex = middleIndex - 1;
            }
        }
        return -1;
    }

3. Двоичный поиск, рекурсивный подход

public static int recursiveBinarySearch(int[] array, int firstElement, int lastElement, int elementToSearch) {
      // условие прекращения
      if (lastElement >= firstElement) {
          int middle = (lastElement + firstElement) / 2;

          // если средний элемент - целевой элемент, вернуть его индекс
          if (array[middle] == elementToSearch) {
              return middle;
          }

          // если средний элемент больше целевого
          // вызываем метод рекурсивно по суженным данным
          if (array[middle] > elementToSearch) {
              return recursiveBinarySearch(array, firstElement, middle - 1, elementToSearch);
          }

          // также, вызываем метод рекурсивно по суженным данным
          return recursiveBinarySearch(array, middle + 1, lastElement, elementToSearch);
      }
      return -1;
  }

4. Поиск прыжками

public static int jumpSearch(int[] array, int elementToSearch) {
    int arrayLength = array.length;
    int jumpStep = (int) Math.sqrt(array.length);
    int previousStep = 0;

    while (array[Math.min(jumpStep, arrayLength) - 1] < elementToSearch) {
        previousStep = jumpStep;
        jumpStep += (int) (Math.sqrt(arrayLength));
        if (previousStep >= arrayLength) {
            return -1;
        }
    }
    while (array[previousStep] < elementToSearch) {
        previousStep++;
        if (previousStep == Math.min(jumpStep, arrayLength)) {
            return -1;
        }
    }

    if (array[previousStep] == elementToSearch) {
        return previousStep;
    }
    return -1;
}

Курс 'Java для начинающих' на Udemy