4.3.4 Searching Algorithms

What is an algorithm?

A set of instructions which completes a task in a finite time and always terminates

What is a searching algorithm?

An algorithm to:

- Find the location of an item in a data structure

- Verify the presence of the item

What are the types of searching algorithm?

- Linear search

- Binary search

- Binary tree search

How does a linear search work?

Each item in the list is checked in sequence until the item is found or all items have been checked

→ Compared with the search term

→ Can be performed on any unordered list

Why are linear searches rarely used?

High time complexity - O(n)

How does a binary search work?

- Midpoint in the list is found

- Determine if the target is higher or lower than the midpoint

- This is repeated until the item is found or the list cannot be divided further

Ordered lists only

What is the time complexity of a binary search?

O(log n) - The list is halved with each search

How does a binary search work?

Identical to a binary search except it is conducted on a binary tree

What is a binary tree?

A rooted ordered tree in which each node has a maximum of two children

What is the time complexity of a binary tree search?

O(log n)