Searching Algorithms

Linear search checks each element one by one until the target is found or the list ends. It works on unsorted data but is O(n). Binary search repeatedly halves a sorted list, achieving O(log n).

def linear_search(data, target):
    """O(n) - checks every element."""
    for i, item in enumerate(data):
        if item == target:
            return i
    return -1

def binary_search(data, target):
    """O(log n) - requires sorted data."""
    low, high = 0, len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 23))  # 5
print(linear_search(numbers, 23))  # 5

For 1,000,000 items, linear search may need 1,000,000 comparisons; binary search needs at most 20.

Sorting Algorithms

Sorting arranges data in a specific order. Bubble sort and selection sort are O(n^2) and good for learning. Merge sort uses divide-and-conquer for O(n log n) performance.

def bubble_sort(data):
    """O(n^2) - repeatedly swap adjacent elements."""
    arr = data[:]
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break  # already sorted
    return arr

def selection_sort(data):
    """O(n^2) - find minimum and place it."""
    arr = data[:]
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]

Merge Sort: Divide and Conquer

Merge sort divides the list in half, recursively sorts each half, then merges the sorted halves. It guarantees O(n log n) in all cases but uses extra memory.

def merge_sort(data):
    """O(n log n) - divide, sort, merge."""
    if len(data) <= 1:
        return data

    mid = len(data) // 2
    left = merge_sort(data[:mid])
    right = merge_sort(data[mid:])
    return merge(left, right)

def merge(left, right):
    """Merge two sorted lists into one."""
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

Key Vocabulary

Big-O Notation

Describes the worst-case growth rate of an algorithm's time or space as input grows (e.g., O(n), O(log n)).

Divide and Conquer

A strategy that breaks a problem into smaller sub-problems, solves each, and combines the results.

In-Place Sorting

Sorting that uses O(1) extra memory by modifying the original array (e.g., bubble sort, selection sort).

Stable Sort

A sort that preserves the relative order of equal elements. Merge sort is stable; selection sort is not.

Worked Examples

1

Trace a binary search for target 23 in [2, 5, 8, 12, 16, 23, 38]

# Step-by-step trace:
# data = [2, 5, 8, 12, 16, 23, 38], target = 23

# Pass 1: low=0, high=6, mid=3 -> data[3]=12 < 23 -> low=4
# Pass 2: low=4, high=6, mid=5 -> data[5]=23 == 23 -> FOUND at index 5

# Only 2 comparisons needed (vs 6 for linear search)

Key insight: Each comparison eliminates half the remaining elements, giving logarithmic performance.

2

Compare sorting algorithm performance

import time
import random

def time_sort(sort_func, data):
    start = time.perf_counter()
    sort_func(data)
    return time.perf_counter() - start

data = random.sample(range(10000), 5000)

t_bubble = time_sort(bubble_sort, data)
t_selection = time_sort(selection_sort, data)
t_merge = time_sort(merge_sort, data)
t_builtin = time_sort(sorted, data)

print(f"Bubble:    {t_bubble:.4f}s")     # ~2.5s
print(f"Selection: {t_selection:.4f}s")   # ~1.2s
print(f"Merge:     {t_merge:.4f}s")       # ~0.03s
print(f"Built-in:  {t_builtin:.4f}s")     # ~0.001s

Observation: O(n log n) algorithms like merge sort dramatically outperform O(n^2) ones on larger datasets. Python's built-in sorted() uses Timsort, a hybrid algorithm.

3

Sort a list of students by grade using a custom key

students = [
    {"name": "Alice", "grade": 88},
    {"name": "Bob", "grade": 95},
    {"name": "Charlie", "grade": 72},
    {"name": "Diana", "grade": 91},
]

# Python's built-in sort with key function
by_grade = sorted(students, key=lambda s: s["grade"], reverse=True)
for s in by_grade:
    print(f"{s['name']}: {s['grade']}")
# Bob: 95
# Diana: 91
# Alice: 88
# Charlie: 72

# Using operator.itemgetter (faster for large datasets)
from operator import itemgetter
by_grade2 = sorted(students, key=itemgetter("grade"))

Real-world sorting often involves complex objects. The key parameter lets you specify what to sort by without modifying the data.

Knowledge Check

Select the correct answer for each question. Click "Check Answer" to see if you are right.

Question 1

What is the time complexity of binary search?

O(n) O(log n) O(n^2) O(1)

Question 2

What prerequisite does binary search require?

The data must be stored in a set The data must contain no duplicates The data must be sorted The data must be numeric

Question 3

What is the time complexity of bubble sort in the worst case?

O(n) O(n log n) O(log n) O(n^2)

Question 4

Which sorting algorithm uses the divide-and-conquer strategy?

Merge sort Selection sort Bubble sort Linear search

Question 5

Python's built-in sorted() function uses which algorithm?

Bubble sort Timsort (hybrid of merge sort and insertion sort) Quick sort Heap sort

Python Algorithms