Binary Search Algorithm vs. Binary Search Tree

The binary search algorithm and the binary search tree (BST) are two distinct concepts that, while related, serve different purposes in computer science.

Binary Search Algorithm

The binary search algorithm is a searching technique used on sorted arrays or containers. It operates by repeatedly dividing the search interval in half.

If the value of the search key is less than the item in the middle of the interval, the algorithm narrows the interval to the lower half.

Otherwise, it narrows it to the upper half. This process continues until the search key is found or the interval is empty.

Key Characteristics:

• Requires Sorted Data: Binary search can only be applied to sorted arrays or containers.
• Time Complexity: $O(log n)$, where n is the number of elements.
• Space Complexity: $O(1)$, as it doesn't require additional space.

The following program uses the standard library’s binary search algorithm:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<int> Numbers{1, 2, 3, 4, 5};
7
8  int target = 4;
9  bool found = std::binary_search(
10    Numbers.begin(), Numbers.end(), target);
11
12  std::cout << "The number " << target
13    << (found ? " was" : " was not") << " found";
14}

1The number 4 was found

Binary Search Tree (BST)

A binary search tree is a data structure that facilitates fast lookup, addition, and removal of items. Each node in the BST has up to two children, referred to as the left child and the right child.

For any node, the left subtree contains values less than the node's value, and the right subtree contains values greater than the node's value.

Key Characteristics:

• Dynamic: BSTs can grow and shrink dynamically, unlike arrays.
• Time Complexity: $O(log n)$ on average for insertion, deletion, and search operations. However, in the worst case (e.g., a completely unbalanced tree), the time complexity can degrade to $O(n)$.
• Space Complexity: $O(n)$, where n is the number of nodes.

The following program creates a binary search tree from scratch:

1#include <iostream>
2
3struct Node {
4  int data;
5  Node* left;
6  Node* right;
7};
8
9Node* newNode(int data) {
10  Node* node = new Node();
11  node->data = data;
12  node->left = nullptr;
13  node->right = nullptr;
14  return node;
15}
16
17Node* insert(Node* root, int data) {
18  if (root == nullptr) {
19    return newNode(data);
20  }
21  if (data < root->data) {
22    root->left = insert(root->left, data);
23  } else if (data > root->data) {
24    root->right = insert(root->right, data);
25  }
26  return root;
27}
28
29bool search(Node* root, int data) {
30  if (root == nullptr) {
31    return false;
32  }
33  if (root->data == data) {
34    return true;
35  }
36  if (data < root->data) {
37    return search(root->left, data);
38  } else {
39    return search(root->right, data);
40  }
41}
42
43int main() {
44  Node* root = nullptr;
45  root = insert(root, 4);
46  insert(root, 2);
47  insert(root, 5);
48  insert(root, 1);
49  insert(root, 3);
50
51  int target = 4;
52  bool found = search(root, target);
53
54  std::cout << "The number " << target
55    << (found ? " was" : " was not") << " found";
56}

1The number 4 was found

Summary

• Binary Search Algorithm: A technique for finding an item in a sorted array with $O(log n)$ time complexity.
• Binary Search Tree: A dynamic data structure that supports fast insertion, deletion, and lookup operations, with $O(log n)$ average time complexity.

Understanding both concepts is crucial for efficient searching and data management in various applications.