🔍 Binary Search — Divide & Conquer in Action

The most classic divide and conquer algorithm is binary search. It finds a value in a sorted list by repeatedly cutting the search area in half.

📖 How Binary Search Works

Look at the middle item of the list
If it is the target — done!
If the target is smaller — search the left half only
If the target is larger — search the right half only
Repeat until found (or the search area is empty)

📖 Analogy: Finding a Word in a Dictionary

Looking up "Python" in a physical dictionary:

Open the dictionary in the middle — you land on "M"
"P" comes after "M" — ignore the first half, focus on M–Z
Open the middle of M–Z — you land on "S"
"P" comes before "S" — ignore S–Z, focus on M–S
Open the middle of M–S — you land on "P" — found it!

You never read every page. You keep halving the search area.

🐍 Python — Binary Search

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

    while low <= high:
        steps = steps + 1
        mid = (low + high) // 2
        guess = sorted_list[mid]

        print("Step", steps, "- Checking index", mid, "=", guess)

        if guess == target:
            print("Found", target, "at index", mid, "in", steps, "steps!")
            return mid
        elif guess < target:
            print("  Too low. Search right half.")
            low = mid + 1
        else:
            print("  Too high. Search left half.")
            high = mid - 1

    print("Not found after", steps, "steps.")
    return -1

# Sorted list of player scores
scores = [12, 23, 34, 45, 56, 67, 78, 89, 90, 95]
print("Searching for 78 in:", scores)
print("")
binary_search(scores, 78)

💡 Try It

Change the target number on the last line (e.g., search for 12, 95, or 50). Watch how the algorithm narrows down the search area each step. Try searching for a number that is not in the list — what happens?