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.