Binary search and binary search tree (BST) are two fundamental concepts in computer science, particularly in the realm of data structures and algorithms. Though they share the concept of "binary" and "search," they are applied in different contexts and solve different problems. This article explores their distinct characteristics, technical details, and practical applications.

Binary Search

Binary search is an efficient algorithm for finding a specific item in a sorted list. Unlike linear search, which scans each element, binary search halves the search space in each step, making it a fundamental algorithm in computer science for quick lookups.

Characteristics of Binary Search

1. Precondition - Sorted Array:
   • Binary search requires the list/array to be sorted beforehand.
   • The efficiency of binary search can only be leveraged with sorted data.
2. Algorithm Detail:
   • Begin with two pointers: `low` at the start and `high` at the end of the array.
   • Compute the middle index `mid` as `(low + high) / 2`.
   • Check if the middle element is equal to the target.
     • If yes, return the index.
     • If the target is smaller, move the `high` pointer to `mid - 1`.
     • If the target is larger, move the `low` pointer to `mid + 1`.
   • Repeat the process until the pointers converge.
3. Time Complexity:
   • Best case: $O(1)$, when the middle element is the target.
   • Average and worst-case: $O(\log n)$, due to the halving strategy.

Example

Let's find the number `7` in the sorted array `[1, 2, 3, 5, 7, 12, 18, 21]`:

5 < 7, move low to mid + 1 = 4

• Each node contains a key, a left child, and a right child.
• The key in each node is greater than any key in its left subtree and less than any key in its right subtree.
• Unlike arrays, BSTs are dynamic and allow for efficient insertions and deletions.
• Balanced variations like AVL trees or Red-Black trees optimize for $O(\log n)$ operations.
• Access, insert, and delete average-case: $O(\log n)$ in a balanced tree.
• Worst-case for unbalanced trees: $O(n)$, similar to a linked list.
• Various traversal methods are possible, including in-order, pre-order, and post-order, which facilitate different operations like sorting and hierarchy extraction.
  3 9 2 5 8 12
• The root node is `7`.
• All nodes in the left subtree of `7` have values less than `7`.
• All nodes in the right subtree of `7` have values greater than `7`.