2.1 Searching and algorithms

Algorithms

An algorithm is a sequence of steps for accomplishing a task. Linear search is a search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached.

Linear search algorithm

OutPut
NUMBERS: 2 4 7 10 11 32 45 87 
Enter a value: 10
Found 10 at index 3.
...
NUMBERS: 2 4 7 10 11 32 45 87 
Enter a value: 17
17 was not found. 

Activity 1: Linear search algorithm execution.

Given list: (20, 4, 114, 23, 34, 25, 45, 66, 77, 89, 11).

  1. How many list elements will be compared to find 77 using linear search?
  2. How many list elements will be checked to find the value 114 using linear search?
  3. How many list elements will be checked if the search key is not found using linear search?

Algorithm runtime

An algorithm's runtime is the time the algorithm takes to execute. If each comparison takes 1 µs (1 microsecond), a linear search algorithm's runtime is up to 1 s to search a list with 1,000,000 elements, 10 s for 10,000,000 elements, and so on. Ex: Searching Amazon's online store, which has more than 200 million items, could require more than 3 minutes.

An algorithm typically uses a number of steps proportional to the size of the input. For a list with 32 elements, linear search requires at most 32 comparisons: 1 comparison if the search key is found at index 0, 2 if found at index 1, and so on, up to 32 comparisons if the the search key is not found. For a list with N elements, linear search thus requires at most N comparisons. The algorithm is said to require "on the order" of N comparisons.

Activity 2: Linear search runtime.

  1. Given a list of 10,000 elements, and if each comparison takes 2 µs, what is the fastest possible runtime for linear search?
  2. Given a list of 10,000 elements, and if each comparison takes 2 µs, what is the longest possible runtime for linear search?