Linear & Binary Search

You have a sorted list of a million customer IDs and need to find one. Looping through every single entry is painfully slow — a linear search checks each element one by one, which becomes unbearable at scale. Instead, binary search can locate the target in a fraction of the steps by repeatedly dividing the search space in half. Understanding both algorithms is crucial because picking the wrong one can mean the difference between a response in milliseconds and one that times out.

The problem this lesson solves

Any time you need to find an item in a collection, you face a core computer science challenge. Without a structured approach, you might write a simple for loop — that's linear search. It works, but its time complexity is O(n). For a list with 1,000 elements, that's up to 1,000 checks. For 1,000,000 elements, it's up to 1,000,000 checks.

Binary search solves this by operating only on sorted data. It achieves O(log n) time complexity: for the same million-element list, it requires at most 20 checks. The catch? Your data must be sorted first. This lesson teaches you both algorithms so you can make the right trade-off for your use case.

Core concept / mental model

Think of linear search like flipping through every page of a phone book to find a name — you start at page 1 and read every single entry. It’s simple but slow.

Binary search is smarter: you open the phone book to the middle. If the name you're looking for comes after that page, you discard the entire first half. Then you repeat with the remaining half, each time cutting your search space in half. You keep doing this until you find the name or conclude it isn't there.

Key insight: Linear search works on any list (sorted or unsorted). Binary search requires a sorted list but is exponentially faster on large datasets.

When to use each

• Linear search: small lists (under ~100 items), unsorted data, or when you need to find the first occurrence quickly.
• Binary search: large sorted datasets, repeated searches, or when you can afford a one-time sort upfront.

How it works step by step

Linear search (sequential search)

1. Start at the first element (index 0).
2. Compare the current element to the target value.
3. If it matches, return the current index.
4. If it doesn't match, move to the next element.
5. Repeat until you find the target or reach the end of the list.
6. If you reach the end without a match, return -1 (or None).

Binary search (divide and conquer)

1. Precondition: the list is sorted in ascending order.
2. Set two pointers: low = 0 and high = len(list) - 1.
3. While low <= high:
   • Calculate mid = (low + high) // 2.
   • Compare list[mid] with the target:
     • Equal: return mid.
     • Greater than target: set high = mid - 1 (search left half).
     • Less than target: set low = mid + 1 (search right half).
4. If the loop ends without returning, the target is not present — return -1.

Hands-on walkthrough

Let's implement both algorithms in Python.

1. Linear search function

def linear_search(arr, target):
    """Return index of target in arr, or -1 if not found."""
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Example usage
numbers = [3, 7, 2, 9, 5, 1, 8]
print(linear_search(numbers, 5))   # Output: 4
print(linear_search(numbers, 10))  # Output: -1

2. Binary search (iterative)

def binary_search(arr, target):
    """Return index of target in sorted arr, or -1 if not found."""
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Example usage on a sorted list
sorted_numbers = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(sorted_numbers, 7))   # Output: 3
print(binary_search(sorted_numbers, 4))   # Output: -1

3. Binary search (recursive)

def binary_search_recursive(arr, target, low, high):
    """Recursive version of binary search."""
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

arr = [1, 3, 5, 7, 9]
# Initial call: low = 0, high = len(arr)-1
print(binary_search_recursive(arr, 7, 0, len(arr)-1))  # Output: 3

Pro tip: The recursive version is elegant but may hit recursion limits on very large arrays. The iterative version is generally preferred in production.

Compare options / when to choose what

When to choose: - Linear search when: data is small (under ~50-100 items), data is frequently changing/unsorted, or you need a quick throwaway solution. - Binary search when: the dataset is large, you can sort once and search often, or performance is critical.

Variation: Interpolation search is a smarter binary search that guesses the position based on value distribution (like opening a dictionary near the letter 'M' when looking for 'Mango'). It can be even faster than binary search on uniformly distributed data but has O(n) worst-case.

Troubleshooting & edge cases

Edge case: duplicate elements

• Linear search: returns the first occurrence (lowest index).
• Binary search: may return any occurrence — it’s not guaranteed to be the first. If you need the first occurrence, do a left-biased binary search.

def leftmost_binary_search(arr, target):
    """Return the first (leftmost) index of target in sorted arr."""
    low, high = 0, len(arr) - 1
    result = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            result = mid
            high = mid - 1  # keep searching left
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return result

What you learned & what's next

You now understand the two fundamental search algorithms in computer science. You can:

• Explain how linear search checks every element (O(n)) and works on unsorted data.
• Explain how binary search cuts the search space in half each step (O(log n)) and requires sorted data.
• Implement both algorithms in Python, including handling edge cases like empty lists and duplicates.
• Choose the right algorithm based on dataset size, sort order, and performance requirements.

Next up: Sorting algorithms — like bubble sort, merge sort, and quicksort — which are the natural companion to binary search. After all, binary search is only as fast as your ability to keep data sorted!