Implementing search

Turn linear search into pseudocode returning an index.

Search implementation

Implementing linear search requires a for loop and an if condition. The loop visits each element; the condition checks equality.

If equality is found, return i immediately returns the index. The loop does not continue because the search is complete.

Early exit

Linear search exits the loop as soon as the target is found. This gives O(1) in the best case: if the target is first, one comparison suffices.

Thanks to early exit, the average case is O(n/2) but Big-O ignores constant factors, so the average is also written O(n).

Exercise Count value

Write count_value(arr, target). Count occurrences and return. Print 3 with print(count_value([1, 2, 2, 3, 2], 2)).

Show example solution

def count_value(arr, target):
    # Count occurrences
    count = 0
    for x in arr:
        if x == target:
            count = count + 1
    return count
print(count_value([1, 2, 2, 3, 2], 2))

Test yourself

Equality check

Equality in array: if arr[i] == ____

Show answer

Equality in array: if arr[i] == target

Implementing search: match the terms

for

Loop
if

Condition
return i

Found
return -1

Not found
What happens when the target is found?
- Loop continues
- Error is raised
- Index is returned
- Array is deleted
Show answer

Index is returned — The index is returned.

Next lesson: Best and worst case

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies