Imagine you have a stack of exam papers and you need to find a specific student's work. You look at each paper, one by one. That's linear search.

What is Linear Search?

Linear search checks every element in a list, one at a time, until it finds the target or reaches the end.

Algorithm:

For each item in the list:
    If the item equals the target:
        Return the item's position
If we reach the end:
    Return -1 (not found)

Key facts:

• Works on any list — sorted or unsorted
• Time complexity: O(n) — checks all n items in worst case

Practice 1

1. Write a function find_name(names, target) using linear search. Return index or -1.
2. Maximum comparisons needed to find an item in 1000 items using linear search?

Implementing Linear Search

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

Practice 2

1. Write linear search that counts how many times a target appears.
2. Write a function using linear search to find the maximum value.

Looking up a word in a dictionary? You open it in the middle, check if your word comes before or after, and discard half the pages. That's binary search!

What is Binary Search?

Binary search repeatedly divides the search interval in half. Only works on sorted data!

Algorithm:

1. Set left = 0, right = len-1
2. While left ≤ right:
   a. mid = (left + right) // 2
   b. If items[mid] == target → Found! Return mid
   c. If items[mid] < target → left = mid + 1
   d. If items[mid] > target → right = mid - 1
3. Not found → Return -1

Practice 1

1. Trace binary search on [2, 5, 8, 12, 16, 23, 38, 45] searching for 23.
2. Maximum comparisons for binary search on 1000 items?

Linear vs Binary Search

Practice 2

1. What happens if you binary search on an unsorted list?
2. Implement binary search for a list of names.