DEV Community

Cover image for Linear Search vs. Binary Search: Which One Should You Use?
Gouranga Das Samrat
Gouranga Das Samrat

Posted on

Linear Search vs. Binary Search: Which One Should You Use?

One works on anything. The other is ten times faster — but has a catch.


The Search Problem

Searching is one of the most fundamental operations in computing. Given a collection of n items, find whether a target value exists — and if so, where.

Two algorithms dominate for searching in arrays:

  • Linear Search — simple, general, O(n)
  • Binary Search — fast, but requires sorting, O(log n)

Choosing between them isn't just about speed — it's about understanding the structure of your data and the trade-offs involved.


Linear Search

How It Works

Linear search (also called sequential search) is the simplest possible approach: scan every element from left to right until you find the target or exhaust the array.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i       # Return index if found
    return -1              # Return -1 if not found
Enter fullscreen mode Exit fullscreen mode

Step-by-Step Example

Array: [15, 3, 42, 8, 27, 6], Target: 27

Check arr[0] = 15  → Not 27, continue
Check arr[1] = 3   → Not 27, continue
Check arr[2] = 42  → Not 27, continue
Check arr[3] = 8   → Not 27, continue
Check arr[4] = 27  → Found! Return 4
Enter fullscreen mode Exit fullscreen mode

5 comparisons to find an element at index 4.

Complexity

Case Comparisons Time Complexity
Best case 1 (target is first) O(1)
Worst case n (not found) O(n)
Average case n/2 O(n)

When to Use Linear Search

  • The array is unsorted (binary search won't work).
  • The array is small (overhead of sorting isn't worth it).
  • You're searching once — sorting first only helps if you'll search many times.
  • The data structure doesn't support random access (e.g., linked lists).
  • You need to find all occurrences (not just the first).

Advantages

  • Works on any array — sorted, unsorted, doesn't matter.
  • Works on any data structure that can be iterated (linked lists, streams).
  • No preprocessing required.
  • Very simple to implement and debug.

Disadvantages

  • Slow for large arrays — O(n) means doubling the array size doubles the time.
  • Not suitable for high-frequency lookups in large datasets.

Binary Search

How It Works

Binary search only works on a sorted array. It repeatedly halves the search space by comparing the target to the middle element:

  1. Look at the middle element.
  2. If it equals the target → done.
  3. If the target is smaller → search the left half.
  4. If the target is larger → search the right half.
  5. Repeat with the remaining half.
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid           # Found
        elif arr[mid] < target:
            low = mid + 1        # Target in right half
        else:
            high = mid - 1       # Target in left half

    return -1                    # Not found
Enter fullscreen mode Exit fullscreen mode

Step-by-Step Example

Sorted array: [3, 6, 8, 15, 27, 42], Target: 27

Step 1: low=0, high=5, mid=2 → arr[2]=8  < 27 → search right half
Step 2: low=3, high=5, mid=4 → arr[4]=27 = 27 → Found! Return 4
Enter fullscreen mode Exit fullscreen mode

Only 2 comparisons instead of 5 with linear search!

The Magic of Halving

Each step cuts the remaining search space in half. Starting with n elements:

After 1 step:  n/2 elements remain
After 2 steps: n/4 elements remain
After 3 steps: n/8 elements remain
After k steps: n/2^k elements remain
Enter fullscreen mode Exit fullscreen mode

We stop when n/2^k = 1, so k = log₂(n).

For n = 1,000,000 elements:

  • Linear search: up to 1,000,000 comparisons
  • Binary search: at most 20 comparisons (log₂(1,000,000) ≈ 20)

Complexity

Case Comparisons Time Complexity
Best case 1 (target is middle) O(1)
Worst case log₂(n) + 1 O(log n)
Average case log₂(n) O(log n)

Recursive Implementation

Binary search can also be written recursively:

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1              # Base case: not found

    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)
Enter fullscreen mode Exit fullscreen mode

The recursive version is cleaner but uses O(log n) stack space. The iterative version uses O(1) space.

A Common Bug: Integer Overflow

In languages with fixed-size integers (like Java or C):

// WRONG — can overflow if low + high > Integer.MAX_VALUE
int mid = (low + high) / 2;

// CORRECT
int mid = low + (high - low) / 2;
Enter fullscreen mode Exit fullscreen mode

Python doesn't have this issue (integers are arbitrary precision), but it's worth knowing for interviews.


Side-by-Side Comparison

Property Linear Search Binary Search
Requirement None Array must be sorted
Best case O(1) O(1)
Worst case O(n) O(log n)
Space complexity O(1) O(1) iterative, O(log n) recursive
Works on linked lists? Yes No (no random access)
Works on unsorted data? Yes No
Simple to implement? Yes Moderate
Preprocessing needed? No Sort first: O(n log n)

When Does Sorting + Binary Search Beat Linear Search?

Suppose you have an unsorted array of n elements, and you'll perform k searches.

  • Linear search for k queries: O(k × n)
  • Sort once + binary search for k queries: O(n log n) + O(k × log n)

Sort + binary search wins when:

k × n  >  n log n + k × log n
k(n - log n)  >  n log n
k  >  n log n / (n - log n)  ≈  log n   (for large n)
Enter fullscreen mode Exit fullscreen mode

Even just log n searches (about 20 for a million elements) makes sorting first worthwhile. In practice, if you're going to search more than once, sort your data.


Variations of Binary Search

Binary search is powerful and generalizable. Common variations:

Find the first occurrence

def first_occurrence(arr, target):
    low, high, result = 0, len(arr) - 1, -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
Enter fullscreen mode Exit fullscreen mode

Find the last occurrence

Same idea, but keep searching right: low = mid + 1 when found.

Binary search on answer

Many optimization problems can be solved with binary search on the answer space, not the data. If you can check "is X feasible?" in O(n) time, binary searching over all possible X values gives O(n log n) total.


Summary

  • Linear search scans sequentially — O(n), works on any array, no preprocessing.
  • Binary search halves the search space — O(log n), but requires a sorted array.
  • The difference is dramatic at scale: binary search makes ~20 comparisons where linear makes 1,000,000.
  • If you search once in an unsorted array: use linear search.
  • If you search many times: sort first, then use binary search.
  • Binary search extends beyond arrays: it applies to any monotone function over an ordered domain.

Next post: Linked Lists — the dynamic, pointer-based alternative to arrays.


Top comments (0)