Searching

Searching a list

• Searching means finding whether a value is in a list, and where.
• The usual answer is the index of the value, or -1 if it is missing.
• Two classic methods are linear search and binary search.

Linear search

• Check each item in turn, from the start.
• Stop as soon as you find a match.
• It works on any list, sorted or not.

names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
    if names[i] == target:
        found = i
        break
print(found)

Binary search

• Binary search needs a sorted list.
• Look at the middle item. If it is the target, stop.
• If the target is smaller, search the left half; if bigger, the right half.

data = [2, 4, 6, 8, 10]
target = 8
low = 0
high = len(data) - 1
found = -1
while low <= high:
    mid = (low + high) // 2
    if data[mid] == target:
        found = mid
        break
    elif data[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
print(found)

Compare them

• Linear search may check every item — slow for a long list.
• Binary search throws away half the list each step, so it is much faster.
• But binary search only works if the data is already sorted.

In Cambridge pseudocode

• Note DIV is whole-number division (Python's //).

// Linear search
FOR i ← 0 TO LENGTH(list) - 1
    IF list[i] = target THEN
        found ← i
    ENDIF
NEXT i

// Binary search (list must be sorted)
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high
    mid ← (low + high) DIV 2
    IF list[mid] = target THEN
        found ← mid
    ELSE
        IF list[mid] < target THEN
            low ← mid + 1
        ELSE
            high ← mid - 1
        ENDIF
    ENDIF
ENDWHILE

Now you try

• Return the index of the value, or -1 when it is not found.
• Press Check answer to test your code.