Какая асимптотическая сложность у алгоритма бинарного поиска?

Асимптотическая сложность бинарного поиска

Главный ответ

Асимптотическая сложность бинарного поиска составляет O(log n), где n — количество элементов в отсортированном массиве. Это логарифмическая сложность, что делает алгоритм исключительно эффективным даже для больших наборов данных.

Почему O(log n)?

Бинарный поиск работает по принципу разделения и завоевания (divide and conquer). На каждой итерации размер поискового диапазона сокращается вдвое:

public class BinarySearch {
    
    // Итеративная реализация - O(log n)
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = 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; // Элемент не найден
    }
}

Математическое доказательство

Если у нас есть n элементов, максимальное количество итераций = log₂(n).

Примеры:

• 8 элементов → макс 3 итерации (log₂8 = 3)
• 16 элементов → макс 4 итерации (log₂16 = 4)
• 1,000,000 элементов → макс 20 итераций (log₂1000000 ≈ 20)

Каждая итерация выполняет постоянное количество операций O(1), поэтому общая сложность = O(log n).

Рекурсивная реализация

Рекурсивный вариант имеет ту же временную сложность O(log n), но добавляет пространственную сложность O(log n) из-за стека вызовов:

public class BinarySearchRecursive {
    
    // Рекурсивная реализация - O(log n) по времени, O(log n) по памяти
    public static int binarySearch(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 binarySearch(arr, target, mid + 1, right);
        } else {
            return binarySearch(arr, target, left, mid - 1);
        }
    }
}

Анализ временной сложности

Best Case (Лучший случай): O(1)

• Элемент найден в середине массива с первой попытки

Average Case (Средний случай): O(log n)

• В среднем требуется примерно половина максимального количества итераций

Worst Case (Худший случай): O(log n)

• Элемент находится в конце или не существует
• Требуется максимум log n итераций

Сравнение с другими алгоритмами поиска

Практический пример с анализом

public class BinarySearchAnalysis {
    
    public static void main(String[] args) {
        // Анализ количества итераций для разных размеров
        int[] sizes = {10, 100, 1000, 10000, 1000000};
        
        for (int size : sizes) {
            int maxIterations = (int) Math.ceil(Math.log(size) / Math.log(2));
            System.out.println("Размер: " + size + 
                             ", макс итераций: " + maxIterations);
        }
        
        // Вывод:
        // Размер: 10, макс итераций: 4
        // Размер: 100, макс итераций: 7
        // Размер: 1000, макс итераций: 10
        // Размер: 10000, макс итераций: 14
        // Размер: 1000000, макс итераций: 20
    }
}

Важные условия для использования

Для гарантированной сложности O(log n) необходимо:

1. Массив должен быть отсортирован - это обязательное условие
2. Прямой доступ к элементам - работает с array и ArrayList, но не LinkedList
3. Сравнимые элементы - должна быть определена операция сравнения

// Поиск в LinkedList будет медленнее из-за отсутствия индексного доступа
LinkedList<Integer> list = new LinkedList<>();
// Даже бинарный поиск здесь будет деградировать ближе к O(n)

// Правильное использование - с массивом или ArrayList
int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15};
int index = binarySearch(sortedArray, 7); // O(log n)

Java Collections API

Java предоставляет встроенную реализацию бинарного поиска:

import java.util.Arrays;
import java.util.Collections;

public class JavaBinarySearch {
    
    public static void main(String[] args) {
        // Для массивов
        int[] arr = {1, 3, 5, 7, 9, 11};
        int index = Arrays.binarySearch(arr, 7); // Возвращает 3
        
        // Для коллекций
        List<Integer> list = Arrays.asList(1, 3, 5, 7, 9, 11);
        int index2 = Collections.binarySearch(list, 7); // Также O(log n)
    }
}

Выводы

• Бинарный поиск имеет сложность O(log n) — логарифмическую
• Это существенно эффективнее, чем линейный поиск O(n)
• Для массива из 1 млн элементов нужно максимум 20 сравнений
• Предусловие: массив должен быть отсортирован
• Это один из фундаментальных алгоритмов в Computer Science