Module 2 Lesson 8: Searching Techniques

Searching is one of the most common tasks in programming. Whether it’s finding a user in a database or a specific score in a high-score list, we need efficient ways to look through data. In this lesson, we will explore the two most fundamental searching methods: Linear Search and Binary Search.

Lesson Overview

In this lesson, we will cover:

Linear Search: The "one-by-one" method.
Binary Search: The "split-and-conquer" method.
The Power of Order: Why sorting makes searching faster.
Case Study: Which one to use when?

1. Linear Search (The Simple Search)

Linear search is the way we naturally search for things when they aren't organized. You start at the beginning and check every item until you find what you’re looking for.

def linear_search(source_list, target):
    for i in range(len(source_list)):
        if source_list[i] == target:
            return f"Found at index {i}"
    return "Not found"

names = ["Sara", "Alex", "Bill", "Jen"]
print(linear_search(names, "Bill")) # Output: Found at index 2

Pros: Works on any list, sorted or unsorted. Cons: Slow on huge lists (if the item is at the end, you have to check everything).

2. Binary Search (The Pro Search)

Imagine searching for a word in a dictionary. You don't start at page 1. You open to the middle. Is your word before or after that page? You just eliminated half the book in one step!

Binary Search only works if the list is SORTED.

def binary_search(sorted_list, target):
    low = 0
    high = len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        
        if sorted_list[mid] == target:
            return f"Found at index {mid}"
        elif sorted_list[mid] < target:
            low = mid + 1 # Search the right half
        else:
            high = mid - 1 # Search the left half
            
    return "Not found"

nums = [10, 20, 30, 40, 50, 60, 70]
print(binary_search(nums, 50)) # Output: Found at index 4

3. Comparing the Two

Linear Search: If you have 1,000,000 items, you might have to do 1,000,000 guesses.
Binary Search: For the same 1,000,000 items, you only need about 20 guesses.

This difference is the difference between a program feeling "instant" and a program feeling "frozen."

Practice Exercise: The Find-a-Friend App

Create a file named search_app.py.

Create a list of 10 friend names, sorted alphabetically.
Write a function is_friend_present(name) that uses Linear Search to find the name.
Write a second function fast_friend_present(name) that uses Binary Search.
Test both functions with a name that is in the list and one that isn't.

Quick Knowledge Check

What is the main requirement for Binary Search to work?
Which search is faster for a list of 5 billion items?
In Linear Search, what is the "worst-case scenario"?
Why is Linear Search still useful if it's slower?

Key Takeaways

Linear Search is simple but slow for large data.
Binary Search is extremely fast but requires sorted data.
Divide and Conquer is the secret to high-performance algorithms.

What’s Next?

If Binary Search needs sorted data, how do we get that data sorted in the first place? In Lesson 9, we’ll look at Sorting Techniques—the algorithms that put things in order!