В чем разница между алгоритмом бинарного поиска и структурой данных «бинарное дерево поиска»?

«В чем разница между алгоритмом бинарного поиска и структурой данных «бинарное дерево поиска»?» — вопрос из категории Алгоритмы и структуры данных, который задают на 10% собеседований Java Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Это принципиально разные сущности: алгоритм vs структура данных.

Аспект Бинарный поиск (Binary Search) Бинарное дерево поиска (Binary Search Tree, BST)
Сущность Алгоритм поиска. Динамическая структура данных.
Условие работы Применяется к отсортированному массиву (или подобному контейнеру с произвольным доступом). Структура строится по правилу: для любого узла X, все ключи в левом поддереве < ключа X < всех ключей в правом поддереве.
Сложность поиска O(log n) (гарантировано, т.к. массив отсортирован). В среднем O(log n), в худшем случае (вырождение в цепочку) O(n).
Вставка/Удаление В массиве: O(n) (требуется сдвиг элементов). В среднем 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;
}

Поиск в BST:

class Node { int key; Node left, right; }

Node searchBST(Node root, int target) {
    if (root == null || root.key == target) return root;
    return (target < root.key) ? searchBST(root.left, target) 
                               : searchBST(root.right, target);
}