Какие известны алгоритмы поиска элемента в массиве?

Линейный поиск (последовательный поиск). Проверяет каждый элемент массива по порядку до тех пор, пока не найдет нужный или не просмотрит весь массив. Прост в реализации, но неэффективен для больших массивов. Сложность: O(n).

// Линейный поиск
public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // Элемент найден, возвращаем индекс
        }
    }
    return -1; // Элемент не найден
}

Бинарный поиск (двоичный поиск). Применяется только для отсортированных массивов. Делит массив пополам, сравнивает искомый элемент с центральным, и продолжает поиск в той половине, где должен находиться элемент. Сложность: O(log n).

// Бинарный поиск (для отсортированного массива)
public int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // Избегаем переполнения

        if (arr[mid] == target) {
            return mid; // Элемент найден, возвращаем индекс
        } else if (arr[mid] < target) {
            low = mid + 1; // Ищем в правой половине
        } else {
            high = mid - 1; // Ищем в левой половине
        }
    }
    return -1; // Элемент не найден
}

Интерполяционный поиск. Улучшенная версия бинарного поиска для равномерно распределенных данных. Использует интерполяционную формулу для определения более точного положения следующего элемента для проверки. Сложность: В среднем O(log log n), в худшем случае O(n).

// Интерполяционный поиск (для отсортированного массива с равномерным распределением)
public int interpolationSearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high && target >= arr[low] && target <= arr[high]) {
        if (low == high) {
            if (arr[low] == target) return low;
            return -1;
        }

        // Интерполяционная формула
        int pos = low + (((high - low) / (arr[high] - arr[low])) * (target - arr[low]));

        if (arr[pos] == target) {
            return pos; // Элемент найден
        } else if (arr[pos] < target) {
            low = pos + 1; // Ищем в верхней части
        } else {
            high = pos - 1; // Ищем в нижней части
        }
    }
    return -1; // Элемент не найден
}