Ответ
Оба алгоритма обеспечивают логарифмическую сложность поиска в среднем случае, но работают с разными структурами данных и имеют разные свойства.
| Критерий | Бинарный поиск | Поиск в бинарном дереве поиска (BST) |
|---|---|---|
| Структура данных | Отсортированный массив (статический). | Динамическая древовидная структура из узлов. |
| Сложность поиска | O(log n) (гарантированно). | O(log n) в среднем, O(n) в худшем (вырожденное дерево). |
| Сложность вставки | O(n) (требуется сдвиг элементов). | O(log n) в среднем. |
| Память | Компактное хранение в массиве. | Дополнительная память на указатели в узлах. |
| Основное применение | Быстрый поиск в статическом, заранее отсортированном наборе данных. | Динамические коллекции, где часто происходят вставки и удаления (например, реализация std::set в C++). |
Пример бинарного поиска по массиву (C++):
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 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 (C++):
struct Node {
int data;
Node* left;
Node* right;
};
Node* searchBST(Node* root, int key) {
// Базовые случаи: дерево пусто или ключ в корне
if (root == nullptr || root->data == key) {
return root;
}
// Ключ меньше корня -> ищем в левом поддереве
if (key < root->data) {
return searchBST(root->left, key);
}
// Ключ больше корня -> ищем в правом поддереве
return searchBST(root->right, key);
}Ключевой вывод: Бинарный поиск — это алгоритм для массива, а BST — это структура данных, которая организует элементы по определенному правилу, позволяя эффективно выполнять не только поиск, но и другие операции.
