Линейный и бинарный поиск

Линейный поиск работает на любых данных. Бинарный требует монотонного порядка и структуры с быстрым доступом по индексу.

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

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

Инвариант перед итерацией i: в диапазоне [0, i) target отсутствует. Время: best O(1), worst O(n), память O(1).

Бинарный поиск

Используем полуинтервал [left, right):

static int binarySearch(int[] sorted, int target) {
    int left = 0;
    int right = sorted.length;
 
    while (left < right) {
        int middle = left + (right - left) / 2;
        int value = sorted[middle];
 
        if (value < target) {
            left = middle + 1;
        } else if (value > target) {
            right = middle;
        } else {
            return middle;
        }
    }
    return -1;
}

left + (right - left) / 2 избегает overflow выражения (left + right) / 2. Инвариант: если target существует, он находится внутри [left, right).

Первое вхождение

При дубликатах обычный поиск возвращает любое вхождение. Lower bound ищет первую позицию >= target:

static int lowerBound(int[] sorted, int target) {
    int left = 0, right = sorted.length;
    while (left < right) {
        int middle = left + (right - left) / 2;
        if (sorted[middle] < target) left = middle + 1;
        else right = middle;
    }
    return left;
}

Target найден, если left < length && sorted[left] == target.

Сортировать несортированный массив ради единственного поиска обычно невыгодно: O(n log n) + O(log n) хуже O(n). Для множества запросов подготовка может окупиться.

На собеседовании

• Главное предусловие binary search? Монотонный порядок по тому же comparator.
• Сложность? O(log n) времени, итеративно O(1) памяти.
• Как найти первое вхождение? Lower bound.
• Почему binary search плох для LinkedList? Доступ к середине O(n).
• Что вернуть для пустого массива? -1, lower bound — 0.