Computer Science - 1 Fundamentals of Algorithms - 4 Searching Algorithms

What is 'searching' in computing?

using a program to look through a list to find a value

What search would you use for a sorted list?

binary search

What search would you use for an unsorted list?

linear search

Binary search [3]

- look at middle value (if even set, use before midpoint)
- discard half without item
- repeat with kept half until item found or not found (not in set)

Linear search

an algorithm that iterates through each item in a list until it finds the target value.

In a sorted list of 2ⁿ items the maximum number of items you need to search is equal to:

n + 1

If the length of the sequence does not fit exactly into 2ⁿ:

use the lower exponent (e.g. 15 is 2³ rather than 2⁴)