Linear Search

#How does it work?

Linear search starts at the beginning and checks the elements one by one to find the target. If it finds it, it returns the index; if it reaches the end, the value isn't there.

It is the simplest search and doesn't need sorted data. It works on anything you can walk through in order: arrays, linked lists, lines of a file.

The price is time: in the worst case (the value is last or missing) every element has to be checked.

#Live animation

for i = 0 to n - 1
  if a[i] == target: return i
return -1

#Step by step

1. 01Start at the first element.
2. 02Compare the element with the target.
3. 03If they are equal, return its index and stop.
4. 04Otherwise move to the next element.
5. 05If you reach the end, the value isn't there; return -1.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def linear_search(a: list[int], target: int) -> int:
    """Returns the index of the first element equal to target, or -1."""
    for i, value in enumerate(a):
        if value == target:
            return i
    return -1


numbers = [4, 8, 1, 9, 3]
print(linear_search(numbers, 9))
print(linear_search(numbers, 7))

#Complexity

If the value is first, one comparison is enough. On average half of the elements are checked, and all of them if the value is missing. If data is sorted once and searched many times, binary search is much faster.

#When to use it?

The right choice for small or unsorted data, one-off searches, and structures without indexed access such as linked lists. Functions like indexOf, includes and find in programming languages do a linear search.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Binary Search
• Naive String Search