Searching - Algorithms

🚶 Linear search — check every item

Linear search walks through a list one item at a time until it finds the target (or runs out). Simple and works on any list, sorted or not. Its speed is O(n).

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i        # found! return the index
    return -1               # not found

print(linear_search([5, 3, 9, 1], 9))   # 2

⚡ Binary search — halve it every time

Binary search only works on a sorted list, but it's lightning fast — O(log n). It checks the middle, then throws away half the list every step.

It's exactly how you find a word in a dictionary: open the middle, decide "earlier" or "later", and repeat on the half that remains.

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1       # target is in the right half
        else:
            high = mid - 1      # target is in the left half
    return -1

🤯 Why halving is a superpower

Searching a sorted list of 1,000,000 items:

Method	Worst-case steps	Big-O
Linear search	1,000,000	O(n)
Binary search	about 20	O(log n)

💡 The catch

Binary search needs the list to be sorted first. If you only search once, sorting may not be worth it. If you search many times, sort once and enjoy fast lookups forever.

✅ What you learned

Linear search: check every item, O(n), works on any list.
Binary search: halve the range each step, O(log n), needs a sorted list.
Return the index when found, or -1 when not.
The midpoint is (low + high) // 2.

🔍 Searching

🚶 Linear search — check every item

⚡ Binary search — halve it every time

🤯 Why halving is a superpower

💡 The catch

✅ What you learned

🎮 Time to Practice!

Task 1: Linear Search

Task 2: Binary Search

Task 3: Count the Steps