Linear search idea

Scan an array front to back to find a target in O(n).

Linear search logic

Linear search is the simplest way to find a target in an array: it checks every element in order from start to end.

If an element equals the target, its index is returned. If the end is reached without a match, -1 is returned.

Complexity analysis

The worst case of linear search is O(n): if the target is last, the whole array is scanned. The best case is O(1): if the target is first.

The average case is also O(n) because the target is on average in the middle and half the array is scanned.

Exercise Linear search

Write linear_search(arr, target). Find target, return index; -1 if not found. Print 2 with print(linear_search([4, 2, 7, 1], 7)).

Show example solution

def linear_search(arr, target):
    # Search for target
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
print(linear_search([4, 2, 7, 1], 7))

Test yourself

What is the worst case of linear search?
- O(1)
- O(log n)
- O(n)
- O(n^2)
Show answer

O(1) — The worst case is O(n).

Not found value

If the target is not found, ____ is returned.

Show answer

If the target is not found, -1 is returned.

Linear search idea: match the terms

Linear search

Check in order
O(n)

Worst case
O(1)

Best case
-1

Not found

Next lesson: Implementing search

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies