Linear Search (College Board AP® Computer Science Principles): Revision Note

Linear search

What is a linear search?

• A linear search (also called a sequential search) checks each element in a list one at a time, from beginning to end, until the target value is found or the end of the list is reached

• It is the simplest search algorithm and works on both sorted and unsorted lists

How a linear search works

• A linear search uses a found flag, initialized to false, to track whether the target has been located

• The loop checks each element in turn; if a match is found the flag is set to true

• After the loop completes, the flag determines what the program displays

found ← false
FOR EACH item IN list
{
   IF(item = target)
   {
      found ← true
   }
}
IF(found = true)
{
   DISPLAY("Found")
}
ELSE
{
   DISPLAY("Not found")
}
 

Linear search characteristics

• Best case: the target is the first element (1 comparison)

• Worst case: the target is the last element or not in the list (n comparisons, where n is the length of the list)

• The number of comparisons grows in proportion to the size of the list

• Linear search does not require the list to be sorted