Linear Search & Binary Search

Jr Codex DSA Notes

Level: Beginner Prerequisites: Module 2, Chapter 7 Time to complete: ~25 minutes

Table of Contents

1. Linear Search Recap
2. Binary Search — Iterative
3. Binary Search — Recursive
4. Why Binary Search Needs Sorted Input
5. Complexity Comparison
6. Variant: Find First Occurrence
7. Variant: Find Last Occurrence
8. Summary & Next Steps

1. Linear Search Recap

You met this in Module 2, Chapter 2: scan every element until you find a match or exhaust the array. It's O(n) and works on any array, sorted or not.

def linear_search(items, target):
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1

2. Binary Search — Iterative

If the array is sorted, you can eliminate half the remaining candidates at every step instead of checking one at a time:

def binary_search(sorted_items, target):
    low, high = 0, len(sorted_items) - 1
 
    while low <= high:
        mid = (low + high) // 2
        if sorted_items[mid] == target:
            return mid
        elif sorted_items[mid] < target:
            low = mid + 1        # target must be in the right half
        else:
            high = mid - 1        # target must be in the left half
 
    return -1
    # O(log n) time, O(1) space

3. Binary Search — Recursive

The same logic, expressed recursively (Module 4 covers recursion in depth — this is a preview):

def binary_search_recursive(sorted_items, target, low=0, high=None):
    if high is None:
        high = len(sorted_items) - 1
    if low > high:
        return -1
 
    mid = (low + high) // 2
    if sorted_items[mid] == target:
        return mid
    elif sorted_items[mid] < target:
        return binary_search_recursive(sorted_items, target, mid + 1, high)
    else:
        return binary_search_recursive(sorted_items, target, low, mid - 1)
    # O(log n) time, O(log n) space — the recursion stack holds one frame per
    # halving, unlike the O(1)-space iterative version (Module 1, Chapter 4)

The recursive version is a clean illustration of the time/space tradeoff from Module 1: same time complexity, but the call stack costs O(log n) space that the iterative loop version doesn't pay.

4. Why Binary Search Needs Sorted Input

Binary search's core move — "the target is bigger than the middle, so it must be in the right half" — is only valid if everything to the left of mid is guaranteed smaller and everything to the right is guaranteed larger. On unsorted data, that guarantee doesn't exist, and eliminating half the array could throw away the answer. Sorting first, then binary-searching repeatedly, is a common and worthwhile tradeoff: an O(n log n) sort (Chapters 4-5) followed by many O(log n) searches beats many O(n) linear searches once you search often enough.

5. Complexity Comparison

For 1,000,000 elements, that's up to 1,000,000 comparisons for linear search versus about 20 for binary search — the same growth-rate gap illustrated in Module 1, Chapter 2.

6. Variant: Find First Occurrence

Standard binary search stops at any match. When duplicates exist, interview problems often ask for the first occurrence specifically — solved by continuing to search left even after finding a match:

def find_first_occurrence(sorted_items, target):
    low, high = 0, len(sorted_items) - 1
    result = -1
 
    while low <= high:
        mid = (low + high) // 2
        if sorted_items[mid] == target:
            result = mid
            high = mid - 1          # keep searching left for an earlier match
        elif sorted_items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
 
    return result
    # Still O(log n) — we're just changing WHICH half we discard on a match

7. Variant: Find Last Occurrence

Mirror image of the previous function — continue searching right after a match:

def find_last_occurrence(sorted_items, target):
    low, high = 0, len(sorted_items) - 1
    result = -1
 
    while low <= high:
        mid = (low + high) // 2
        if sorted_items[mid] == target:
            result = mid
            low = mid + 1           # keep searching right for a later match
        elif sorted_items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
 
    return result
 
items = [1, 2, 2, 2, 3, 4]
print(find_first_occurrence(items, 2))   # 1
print(find_last_occurrence(items, 2))    # 3

Together, these two give you the count of any value in a sorted array in O(log n) (last - first + 1), instead of O(n) by scanning.

8. Summary & Next Steps

Key Takeaways

• Linear search works on any array in O(n); binary search needs sorted input but achieves O(log n).
• Binary search's core assumption — everything left of mid is smaller, everything right is larger — is exactly why it requires sorted data.
• The recursive version has the same time complexity but costs O(log n) extra space for the call stack; the iterative version is O(1) space.
• First/last-occurrence variants adjust which half is discarded on a match, without changing the O(log n) complexity.

Concept Check

1. Why does binary search fail silently (or give wrong answers) on unsorted data, rather than just being slow?
2. Why does the recursive binary search use O(log n) space while the iterative version uses O(1)?
3. How would you use find_first_occurrence and find_last_occurrence together to count how many times a value appears in a sorted array, in O(log n)?

Next Chapter

→ Chapter 2: Bubble Sort & Selection Sort

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index