Algorithms: searching

What we'll do

• An algorithm is a clear list of steps that solves a problem.
• A very common job is searching: find where a value is in a list.
• We will learn two algorithms: linear search and binary search.

Linear search

• Check the items one by one, from start to end.
• If you find the value, return its index (position).
• If you reach the end and never find it, return -1.

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1

print(linear_search([4, 8, 15, 16], 15))
print(linear_search([4, 8, 15, 16], 99))

Why a sorted list helps

• Linear search works on any list, even a messy one.
• But if the list is sorted (small to big), we can be much faster.
• Binary search uses the sorted order to skip half the list each time.

Binary search

• Look at the middle item.
• If it is the target, you are done.
• If the target is smaller, search the left half; if bigger, the right half. Repeat.

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

print(binary_search([1, 3, 5, 7, 9], 7))
print(binary_search([1, 3, 5, 7, 9], 4))

Putting ideas together

• A search combines three building blocks you already know.
• Sequencing: do steps in order. Selection: if / elif / else.
• Iteration: a loop (for or while) repeats the check.

In AP CSP pseudocode

• The exam writes a loop and a check like this.
• FOR EACH visits every item; IF selects; REPEAT UNTIL loops until a test is true.

PROCEDURE contains(list, target)
{
    FOR EACH item IN list
    {
        IF (item = target)
        {
            RETURN(true)
        }
    }
    RETURN(false)
}

Common mistakes

• Binary search needs a sorted list.
• Linear search checks each item in turn.

Now you try

• Each task gives a procedure name and what it must return.
• Press Check answer to test your code.