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

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

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;       // нашли
        if (arr[mid] < target) left = mid + 1;     // искомое правее середины
        else right = mid - 1;                       // искомое левее середины
    }
    return -1;   // не нашли
}

Главное условие — массив должен быть отсортирован. На неотсортированных данных бинарный поиск просто не работает корректно.

Копнуть глубже

Почему O(log n). На каждом шаге область поиска уменьшается вдвое. Для массива из миллиона элементов хватит всего ~20 шагов (2²⁰ ≈ миллион) — против миллиона шагов у линейного перебора. Это и есть разница между O(n) и O(log n) на практике.

Готовое решение в Java — не нужно писать вручную:

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

🎤 Закрыл тему, если можешь объяснить:

• идею бинарного поиска и обязательное условие (отсортированность);
• почему сложность именно O(log n) (если дошёл до 2-го слоя).