A searching algorithm is an algorithm to find the index of an item in a list.

For example, the index of 51 in the list [61, 7, 26, 51, 39, 35, 18, 65] is 3.
Note: in Computer Science, the first item of a list is at index 0, NOT index 1.

Linear search is a searching algorithm which checks each item in order.

Example 1 shows an implementation of linear search in pseudo-code.

Example 1
SUBROUTINE linearSearch(list, item)
  FOR i ← 0 TO LEN(list)-1
    IF list[i] = item THEN
      RETURN i
    ENDIF
  ENDFOR
  RETURN -1
ENDSUBROUTINE

Diagram 4 in 1.03 (Flowcharts) shows a flowchart implementation of linear search.

The steps to do a linear search are as follows:
  1. Look at the first item in your list
  2. Check if this is the item that you are looking for
  3. If it is, output the index and exit
  4. Otherwise, move on to the next item in the list
  5. Repeat steps 2 to 4 until you find the item, or you reach the end of the list

---

What is the maximum number of comparisons linear search would need to do for a list of length n?

n comparisons (if the item isn't in the list, or it is at the very end). This is called the worst case time complexity, and is written as O(n).

---