Explicați diferența dintre algoritmul de căutare binară și structura de date arbore binar de căutare.

Алгоритм бинарного поиска и структура данных двоичного дерева поиска (BST) связаны с поиском, но различаются по сути и применению:

• Бинарный поиск — это алгоритм, который ищет элемент в отсортированном массиве, последовательно деля область поиска пополам. Он работает за O(log n) времени, но требует, чтобы данные были в виде отсортированного массива или списка.

• Двоичное дерево поиска (BST) — это структура данных, представляющая собой дерево, где у каждого узла левый потомок содержит значение меньше узла, а правый — больше. BST позволяет эффективно вставлять, удалять и искать элементы, обычно за 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;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // не найдено
}

Пример узла BST:

class Node {
    int value;
    Node left, right;
    Node(int value) { this.value = value; }
}