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

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

Поиск — одна из фундаментальных операций в информатике. Выбор алгоритма критически влияет на производительность приложения, особенно при работе с большими объёмами данных.

1. Линейный поиск (Linear Search)

Проходит по массиву последовательно, сравнивая каждый элемент.

public class LinearSearch {
    // Сложность: O(n), где n — размер массива
    // Память: O(1)
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // Нашли
            }
        }
        return -1; // Не найдено
    }
}

Используй когда:

• Массив не отсортирован
• Массив маленький
• Элемент вероятно в начале массива

Плюсы: работает с неотсортированными данными. Минусы: медленный для больших массивов.

2. Бинарный поиск (Binary Search)

Делит массив пополам на каждом шаге. Требует отсортированный массив!

public class BinarySearch {
    // Сложность: O(log n)
    // Память: O(1) для итеративной версии
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // Защита от overflow
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1; // Ищем в правой половине
            } else {
                right = mid - 1; // Ищем в левой половине
            }
        }
        return -1;
    }
    
    // Рекурсивная версия
    public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) return -1;
        
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binarySearchRecursive(arr, target, mid + 1, right);
        } else {
            return binarySearchRecursive(arr, target, left, mid - 1);
        }
    }
}

Используй когда:

• Массив отсортирован
• Нужна высокая производительность
• Большой объём данных

Пример: Поиск в отсортированном списке с 1 миллионом элементов требует максимум 20 сравнений (log₂(1000000) ≈ 20)!

3. Поиск в отсортированной матрице (Search a 2D Matrix)

Отсортированная матрица как граф — можно начать с верхнего правого угла.

public class Matrix2DSearch {
    // Сложность: O(m + n)
    // Память: O(1)
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        
        int row = 0;
        int col = matrix[0].length - 1; // Начинаем с верхнего правого
        
        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--; // Идём влево
            } else {
                row++; // Идём вниз
            }
        }
        return false;
    }
}

4. Поиск элемента в rotated sorted array

Массив отсортирован, но затем повёрнут (rotated).

public class RotatedArraySearch {
    // Сложность: O(log n)
    // Память: O(1)
    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }
            
            // Определяем, какая половина отсортирована
            if (nums[left] <= nums[mid]) { // Левая половина отсортирована
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1; // target в левой половине
                } else {
                    left = mid + 1; // target в правой половине
                }
            } else { // Правая половина отсортирована
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1; // target в правой половине
                } else {
                    right = mid - 1; // target в левой половине
                }
            }
        }
        return -1;
    }
}

5. Интерполяционный поиск (Interpolation Search)

Улучшение бинарного поиска для равномерно распределённых данных.

public class InterpolationSearch {
    // Сложность: O(log log n) в среднем, O(n) в худшем случае
    // Память: O(1)
    public static int interpolationSearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right && target >= arr[left] && target <= arr[right]) {
            // Интерполяция позиции вместо деления пополам
            int pos = left + (right - left) * (target - arr[left]) / 
                      (arr[right] - arr[left]);
            
            if (arr[pos] == target) {
                return pos;
            } else if (arr[pos] < target) {
                left = pos + 1;
            } else {
                right = pos - 1;
            }
        }
        return -1;
    }
}

Используй когда: данные равномерно распределены (например, индексы в БД).

6. Exponential Search

Удваивает диапазон поиска, пока не найдёт элемент, потом применяет бинарный поиск.

public class ExponentialSearch {
    // Сложность: O(log n)
    // Память: O(1)
    public static int exponentialSearch(int[] arr, int target) {
        if (arr[0] == target) return 0;
        
        int bound = 1;
        while (bound < arr.length && arr[bound] < target) {
            bound *= 2; // Экспоненциальный прыжок
        }
        
        // Бинарный поиск в диапазоне
        int left = bound / 2;
        int right = Math.min(bound, arr.length - 1);
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

7. Поиск с использованием HashSet

Для частых поисков с быстрой предварительной подготовкой.

public class HashSetSearch {
    private Set<Integer> set;
    
    // Конструктор: O(n), где n — размер массива
    public HashSetSearch(int[] arr) {
        set = new HashSet<>(Arrays.asList(
            Arrays.stream(arr).boxed().toArray(Integer[]::new)
        ));
    }
    
    // Поиск: O(1) в среднем
    public boolean contains(int target) {
        return set.contains(target);
    }
}

8. Two Pointer Search

Для проверки парных элементов (например, в отсортированном массиве).

public class TwoPointerSearch {
    // Найти пару элементов, которые в сумме дают target
    // Сложность: O(n)
    // Память: O(1)
    public static boolean twoSumSearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        
        while (left < right) {
            int sum = arr[left] + arr[right];
            
            if (sum == target) {
                return true;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }
}

Сравнительная таблица

Практический совет

В реальных приложениях часто используется Collections.binarySearch() в Java:

List<Integer> list = Arrays.asList(1, 3, 5, 7, 9);
int index = Collections.binarySearch(list, 5); // 2

Или Arrays.binarySearch() для массивов:

int[] arr = {1, 3, 5, 7, 9};
int index = Arrays.binarySearch(arr, 5); // 2

Выбор алгоритма поиска зависит от характеристик данных, их размера и частоты поисков. Для критичных мест кода анализ сложности — не опция, а необходимость.