Lesson 1: Linear Search vs Binary Search

The Dictionary Story

Imagine you're looking up the word "serendipity" in a physical dictionary.

Method 1 — The Slow Way: You start at page one. "Aardvark." Nope. "Abandon." Nope. You flip page after page, word after word, scanning every single entry from A to Z until you finally reach "serendipity" somewhere in the S section. This is linear search: check every item until you find what you need.

Method 2 — The Smart Way: You open the dictionary to the middle. You're on the M section. "Serendipity" comes after M, so you throw away the first half entirely. You open the remaining half to its middle — you're now in the R section. Still before S, so throw away this half too. You keep halving the search space until you land directly on "serendipity" in just a handful of moves.

That's binary search — and the difference in speed is staggering.

Why This Matters

"The right algorithm for the job is worth more than the fastest hardware you can buy."

Understanding when to use each approach is one of the most fundamental skills in programming. It's also one of the most tested topics in technical interviews.

Linear Search

How It Works

Linear search is the simplest possible searching strategy: start at the beginning, check each element one by one, stop when you find your target (or reach the end).

def linear_search(arr, target):
    for i in range(len(arr)):          # Loop through every index
        if arr[i] == target:           # Check if current element matches
            return i                   # Found it — return the index
    return -1                          # Target not found in the array

# --- Example ---
fruits = ["apple", "mango", "banana", "kiwi", "grape"]
result = linear_search(fruits, "kiwi")
print(f"Found 'kiwi' at index: {result}")

Input: ["apple", "mango", "banana", "kiwi", "grape"], target = "kiwi"

Output:

Found 'kiwi' at index: 3

What happened step by step:

• Index 0: "apple" — no match
• Index 1: "mango" — no match
• Index 2: "banana" — no match
• Index 3: "kiwi" — match found, return 3

Complexity

Key property: Works on any data — sorted or unsorted, any data type.

Binary Search

The Precondition: Data Must Be Sorted

Binary search has one strict requirement: the array must be sorted. This is not optional. If your data is unsorted, binary search will give you wrong answers.

This creates an important trade-off: sorting costs O(n log n). If you only need to search once, linear search on unsorted data might actually be cheaper. Binary search pays off when you search the same sorted dataset many times.

Why Is It O(log n)?

Here's the magic. Each comparison eliminates half of the remaining elements.

Start with n = 1,000,000,000 (1 billion) elements

After comparison 1:  500,000,000 elements remain
After comparison 2:  250,000,000 elements remain
After comparison 3:  125,000,000 elements remain
...
After comparison 30:         1 element remains

30 comparisons to search 1 billion elements. That's log₂(1,000,000,000) ≈ 30.

Compare that to linear search, which might need up to 1 billion comparisons on the same dataset.

Iterative Implementation

def binary_search_iterative(arr, target):
    left = 0                           # Left boundary starts at index 0
    right = len(arr) - 1               # Right boundary starts at last index

    while left <= right:               # Keep searching while range is valid
        mid = left + (right - left) // 2   # Find middle (avoids integer overflow)

        if arr[mid] == target:         # Found the target
            return mid
        elif arr[mid] < target:        # Target is in the RIGHT half
            left = mid + 1             # Move left boundary past mid
        else:                          # Target is in the LEFT half
            right = mid - 1            # Move right boundary before mid

    return -1                          # Target not in array

# --- Example ---
numbers = [3, 7, 12, 19, 25, 31, 44, 58, 63, 70]
result = binary_search_iterative(numbers, 31)
print(f"Found 31 at index: {result}")

Input: [3, 7, 12, 19, 25, 31, 44, 58, 63, 70], target = 31

Traced execution:

Array:  [3, 7, 12, 19, 25, 31, 44, 58, 63, 70]
Index:   0  1   2   3   4   5   6   7   8   9

Step 1: left=0, right=9, mid=4  → arr[4]=25 < 31  → search RIGHT half
Step 2: left=5, right=9, mid=7  → arr[7]=58 > 31  → search LEFT half
Step 3: left=5, right=6, mid=5  → arr[5]=31 == 31 → FOUND at index 5

Output:

Found 31 at index: 5

Recursive Implementation

def binary_search_recursive(arr, target, left, right):
    if left > right:                   # Base case: range is empty, not found
        return -1

    mid = left + (right - left) // 2   # Calculate midpoint

    if arr[mid] == target:             # Found the target
        return mid
    elif arr[mid] < target:            # Target in right half — recurse right
        return binary_search_recursive(arr, target, mid + 1, right)
    else:                              # Target in left half — recurse left
        return binary_search_recursive(arr, target, left, mid - 1)

# --- Example ---
numbers = [3, 7, 12, 19, 25, 31, 44, 58, 63, 70]
result = binary_search_recursive(numbers, 12, 0, len(numbers) - 1)
print(f"Found 12 at index: {result}")

Output:

Found 12 at index: 2

Common Mistake: Off-By-One Errors

The most frequent bug in binary search is getting the boundary conditions wrong. Here are the two dangerous versions:

Wrong (infinite loop risk):

mid = (left + right) // 2
left = mid    # BUG: if left == mid, left never advances

Wrong (misses elements):

while left < right:   # BUG: stops one step too early, misses the last element

Correct pattern:

while left <= right:          # <= ensures single-element ranges are checked
    mid = left + (right - left) // 2   # Safe midpoint calculation
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        left = mid + 1        # +1 skips mid (already checked), prevents loop
    else:
        right = mid - 1       # -1 skips mid, prevents loop

The formula left + (right - left) // 2 instead of (left + right) // 2 also prevents integer overflow when left and right are very large numbers — a real issue in languages like Java and C++.

Linear vs Binary Search: When to Use Each

Real-World Applications

Binary Search in the Wild:

• Database indexes — B-tree indexes use binary search principles to find rows in milliseconds across millions of records
• Phone directories — traditional phonebooks were searched this way mentally
• Git bisect — the git bisect command uses binary search to find which commit introduced a bug
• System calls — bsearch() in C standard library, Python's bisect module
• Package managers — searching sorted package registries for version compatibility

Linear Search in the Wild:

• Searching unsorted log files for an error message
• Finding a contact whose name you're not sure about
• Checking if a username exists in a small user list
• Any case where sorting would cost more than the search saves

Interview Relevance

Binary search appears in interviews far beyond simple "find a value" questions. Once you internalize the pattern — repeatedly halving a search space based on a condition — you'll recognize it in:

• "Find the minimum value satisfying condition X"
• "Find the square root of N to K decimal places"
• "What is the earliest day a task can be completed?"

All of these are binary search on an answer space, not just an array.

The golden rule: If your data is sorted (or sortable) and you're searching it more than once, binary search is almost always the right choice.