2: Searching, Binary Search Trees and Heaps

Unit Introduction

Searching is one of the most fundamental problems in Computer Science. It is the process of finding a particular item in a collection of items. Typically, a search answers whether the item is present in the collection or not. This unit discusses two important search methods: sequential search and binary search. A Sequential (linear) search is the simplest method to solve the searching problem. It finds an item in a collection by looking for it in a collection one at a time from the beginning till the end. Binary Search on the other hand is use a divide and conquer strategy. In divide and conquer, a larger problem is reduced into smaller sub-problems recursively until the problem is small enough that the solution is trivial. A condition for binary search is that the array should be a sorted array.

The unit also discusses two important data structures; a binary search tree (BST) and a heap. A BST is a binary tree based data structure that is viewed to support efficiently the dynamic set operations, including search and insert operations amongst others. A heap on the other hand is a specific tree based data structure in which all the nodes of tree are in a specific order. The maximum number of children of a node in the heap depends on the type of heap. However, a binary heap is the most commonly used heap type, where there are at most 2 children of a node.