Learn > Higher Computing Science > Software Design and Development > Implementation > Standard Algorithms > Linear Search

Linear search

Linear search looks through an array one item at a time until the target value is found, or the array ends. When a match is found, the algorithm records the position (index) where the item is stored. This position can then be displayed straight away (for example, “Found at position 3”) or it can be stored in a variable so that the program can use it later.

There are two main versions of linear search:

  • Search for all occurrences
    • This version continues searching the array until the very end, even if a match has already been found.
    • It is used when the same value might appear more than once and you need to know the position of every match.
    • Example use: finding every student who scored grade “A” in a class results array.
  • Search for the first occurrence
    • This version stops as soon as a match is found, without checking the rest of the array.
    • It is used when all values in the array are unique, or when you only care about the first time a value appears.
    • Example use: finding the first available seat in a booking system.
def linear_search(array, target):
    found = False
    pos = 0

    while found == False and pos < len(array):
        if array[pos].name == target:
            found = True
        else:
            pos = pos + 1

    if found == True:
        print("Found at position", pos)
    else:
        print("Not found")

Linear search - all occurrences

def linear_search(array, target):
    for i in range(len(array)):
        if array[i] == target:
            print("Found at position", i)


	
def linear_search(array, target): 
    for i in range(len(array)): 
        if array[i].name == target: 
            print("Found at position", i)

Linear search - first occurrence

def linear_search(array, target):
    found = False
    pos = 0

    while found == False and pos < len(array):
        if array[pos] == target:
            found = True
        else:
            pos = pos + 1

    if found == True:
        print("Found at position", pos)
    else:
        print("Not found")


	
def linear_search(array, target):
    found = False
    pos = 0

    while found == False and pos < len(array):
        if array[pos].name == target:
            found = True
        else:
            pos = pos + 1

    if found == True:
        print("Found at position", pos)
    else:
        print("Not found")