Linear search in Python

Linear search checks the items of a list one by one, from the start, until it finds the target. If it reaches the end without finding it, the target is not in the list.

The program

def linear_search(items, target):
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1                          # checked every item: not found

names = ["Linus", "Ada", "Hedy", "Alan", "Grace", "Ada"]
print(linear_search(names, "Hedy"))
print(linear_search(names, "Ada"))
print(linear_search(names, "Margaret"))
print(linear_search([], "Ada"))

2
1
-1
-1

How it works

• enumerate(items) gives the position i and the item together, so the function can return the position.
• return i stops the loop at the first match. "Ada" is at positions 1 and 5, and the function returns 1.
• -1 means "not found". It cannot be confused with a real position, because positions start at 0.
• The list does not need to be sorted. Binary search needs a sorted list; linear search works on any list.
• Python's own names.index("Hedy") does the same search, but it raises a ValueError when the item is missing. "Hedy" in names gives only True or False.

Counting comparisons

Each loop step compares one item with the target. Here both searches count their comparisons on a sorted list of 1,000,000 even numbers:

def linear_search_count(items, target):
    comparisons = 0
    for i, item in enumerate(items):
        comparisons += 1
        if item == target:
            return i, comparisons
    return -1, comparisons

def binary_search_count(items, target):
    comparisons = 0
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        comparisons += 1
        if items[mid] == target:
            return mid, comparisons
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, comparisons

numbers = list(range(0, 2_000_000, 2))
for target in [10, 1_999_998, 7]:
    print(target, linear_search_count(numbers, target), binary_search_count(numbers, target))

10 (5, 6) (5, 20)
1999998 (999999, 1000000) (999999, 20)
7 (-1, 1000000) (-1, 20)

Linear search is fast when the target is near the start, but in the worst case it checks every item. Binary search needs at most about 20 checks for a million items, but only on a sorted list. For one search in an unsorted list, linear search is the right choice, because sorting first takes longer than the search. See binary search for how it works.