Binary Search in C++

Binary Search Algorithm vs. Binary Search Tree

What is the difference between a binary search algorithm and a binary search tree?

Abstract art representing computer programming

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(logn)O(log n), where n is the number of elements.
  • Space Complexity: O(1)O(1), as it doesn't require additional space.

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

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> Numbers{1, 2, 3, 4, 5};

  int target = 4;
  bool found = std::binary_search(
    Numbers.begin(), Numbers.end(), target);

  std::cout << "The number " << target
    << (found ? " was" : " was not") << " found";
}
The 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(logn)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)O(n).
  • Space Complexity: O(n)O(n), where n is the number of nodes.

The following program creates a binary search tree from scratch:

#include <iostream>

struct Node {
  int data;
  Node* left;
  Node* right;
};

Node* newNode(int data) {
  Node* node = new Node();
  node->data = data;
  node->left = nullptr;
  node->right = nullptr;
  return node;
}

Node* insert(Node* root, int data) {
  if (root == nullptr) {
    return newNode(data);
  }
  if (data < root->data) {
    root->left = insert(root->left, data);
  } else if (data > root->data) {
    root->right = insert(root->right, data);
  }
  return root;
}

bool search(Node* root, int data) {
  if (root == nullptr) {
    return false;
  }
  if (root->data == data) {
    return true;
  }
  if (data < root->data) {
    return search(root->left, data);
  } else {
    return search(root->right, data);
  }
}

int main() {
  Node* root = nullptr;
  root = insert(root, 4);
  insert(root, 2);
  insert(root, 5);
  insert(root, 1);
  insert(root, 3);

  int target = 4;
  bool found = search(root, target);

  std::cout << "The number " << target
    << (found ? " was" : " was not") << " found";
}
The number 4 was found

Summary

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

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

This Question is from the Lesson:

Binary Search in C++

An introduction to the advantages of binary search, and how to use it with the C++ standard library algorithms binary_search(), lower_bound(), upper_bound(), and equal_range()

Answers to questions are automatically generated and may not have been reviewed.

This Question is from the Lesson:

Binary Search in C++

An introduction to the advantages of binary search, and how to use it with the C++ standard library algorithms binary_search(), lower_bound(), upper_bound(), and equal_range()

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved