Searching is a problem you'll solve constantly, and the algorithm you reach for depends entirely on one question: is your data sorted? Linear search doesn't care either way, but it's slow. Binary search is dramatically faster — but only works if the data is already sorted.

Linear Search: Check Everything

Linear search is the brute-force approach: start at the beginning and check every element one by one until you find a match (or run out of elements). It makes no assumptions about the data's order, which is both its strength and its weakness.

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

numbers = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(numbers, 22))
print(linear_search(numbers, 99))

Output:

4
-1

In the worst case (the target is the last element, or isn't present at all), linear search examines every single element — O(n) time. Its one real advantage: it works on any list, sorted or not, and needs no preprocessing.

Binary Search: Eliminate Half Each Time

Binary search requires the data to be sorted first, but in exchange, it's dramatically faster. Instead of checking elements one at a time, it checks the middle element and uses the fact that the array is sorted to immediately discard an entire half: if the target is smaller than the middle value, it must be in the left half (if it's present at all); if larger, the right half. Repeating this halves the search space every single step.

def binary_search(arr, target):
    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

sorted_numbers = [11, 12, 22, 25, 34, 64, 90]
print(binary_search(sorted_numbers, 22))
print(binary_search(sorted_numbers, 99))

Output:

2
-1

O(n) vs O(log n): Why the Gap Is Huge

The difference looks small on paper but compounds fast. Searching a sorted list of 1,000,000 elements, linear search might check up to a million elements in the worst case. Binary search needs at most about 20 comparisons (log₂ 1,000,000 ≈ 20), since each comparison eliminates half the remaining data. That gap only widens as data grows — doubling the input size adds just one extra comparison to binary search, while it doubles linear search's worst-case work.

The Catch: Binary Search Needs Sorted Data

This speed isn't free. If your data isn't sorted, you either sort it first (which costs at least O(n log n), as covered in the sorting algorithms overview) or you're stuck with linear search. That upfront sorting cost only pays off if you're going to search the same dataset many times — sort once, then enjoy O(log n) lookups on every subsequent search. For a one-off search on unsorted data, linear search's O(n) is actually the better overall deal, since sorting first would cost more than just scanning once. For a runnable, fully worked version with both iterative and recursive implementations, see the binary search program example.