## Lesson 04: Linear and Binary Search

### Specification Points Addressed in this lesson:

- Understand and explain how the linear search algorithm works.
- Understand and explain how the binary search algorithm works.
- Compare and contrast linear and binary search algorithms.
- Understand that more than one algorithm can be used to solve the same problem.
- Compare the efficiency of algorithms explaining how some algorithms are more efficient than others in solving the same problem.

**1. Linear Search**

The Linear search algorithm

- Start at the beginning of the list
**Compare**each element with the key- IF they are the same THEN item found
- ELSE
**compare**next element - Repeat the
**comparison**until we either find the element or reach the end of the list. - If we are at the end of the list and the element is not found then the element is not in the list.

In the example below the key (3) was found after 6 comparisons.

Here is the pseudo-code for the linear search algorithm.

```
SUBROUTINE linearSearch(key)
found ← FALSE
position ← 0
WHILE position < LEN(list) AND NOT found
IF list[position] = key THEN
OUTPUT key, "found at position", position+1
found ← TRUE
ELSE
position ← position + 1
ENDIF
{if the key is not in the list}
IF position = LEN(list) THEN
OUTPUT key, "is not in the list"
ENDIF
ENDWHILE
ENDSUBROUTINE
```

The input to the subroutine is the key – item that we are trying to find. The algorithm starts by creating a boolean variable called **found** and assigning the value **FALSE** to the variable; an integer variable called **position** is also created, and the value **0** is assigned to it.

The statements in the **WHILE **loop execute as long as we are not at the end of the list (*position < LEN(list) )* **AND** we have yet to find the item. If one of those conditions is met, then the WHILE loop terminates.

In the **WHILE** loop, we use an **IF** statement to check if the item we are currently looking at is the same as the key. If they are the same, we print *“found at position”* and set the Boolean variable to True (this will break the WHILE loop).

If the key differs from the current item, we increment the position to move on to the next item in the list.

The last **IF** statement checks that if we get to the end of the list and have not found the item, we print a message to inform the user.

### 2. Binary Search

In general, the binary search is more efficient than the linear search on a larger list; however, the list must be sorted to use the binary search. Here is the algorithm for the binary search.

- Compare the key with the middle value
- If they are the same, stop; we have found our value
- If the middle value is greater than the key, then carry out the binary search on the bottom half of the list.
- If the middle value is less than the key, then carry out the binary search on the top half of the list.

Here is the pseudo-code for the binary search:

```
SUBROUTINE binarySearch(key)
low ← 0
high ← LEN(array) - 1
WHILE high >= low
midPosition ← (low + high) DIV 2
midValue ← array[ midPosition ]
IF (midValue < key ) THEN
low ← midPosition + 1
ELSE
IF (midValue > key) THEN
high ← midPosition - 1
ELSE
RETURN midPosition
ENDIF
ENDIF
ENDWHILE
RETURN -1 # not in list
ENDSUBROUTINE
```

### 3. Comparing Linear and Binary Search

- Binary search and linear search will both find an element in a list.
- Binary search only works on a
__sorted list__, while linear search can work on any list. - Binary search will find the element with fewer
**comparisons**__on average__than linear search - If the list is short, both algorithms perform at the same rate.