Linear vs Binary Search

Linear search checks each element one by one until it finds the target, running in O(n) time. Binary search repeatedly halves a sorted array, discarding half the remaining elements at each step, running in O(log n). Binary search is vastly faster, but it pays a price: the data must already be sorted. That single requirement decides which one you can use.

Linear search: simple and universal

Linear search makes no assumptions. It walks the array from the first element to the last, comparing each with the target. If it finds a match, it returns the index; if it reaches the end without a match, the target is not present.

#include <iostream>
using namespace std;

// Return the index of target, or -1 if not found.
// Worst case scans every element: O(n).
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;       // found it at index i
        }
    }
    return -1;              // checked everything, not present
}

int main() {
    int arr[] = {4, 2, 7, 1, 9, 3};   // works on unsorted data
    cout << linearSearch(arr, 6, 7) << endl; // 2
    cout << linearSearch(arr, 6, 5) << endl; // -1
    return 0;
}

Linear search works on any data, sorted or not. Its weakness is speed: for a million elements, the worst case is a million comparisons.

Binary search: halve and conquer

Binary search needs a sorted array. It looks at the middle element. If that is the target, it is done. If the target is smaller, it can ignore the entire upper half; if larger, it ignores the lower half. Each comparison eliminates half the remaining elements, so it homes in on the answer in about log2(n) steps.

#include <iostream>
using namespace std;

// Return the index of target in a SORTED array, or -1 if not found.
// Each step halves the search range: O(log n).
int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // avoids overflow vs (low+high)/2
        if (arr[mid] == target) {
            return mid;            // found it
        } else if (arr[mid] < target) {
            low = mid + 1;         // target must be in the upper half
        } else {
            high = mid - 1;        // target must be in the lower half
        }
    }
    return -1;                     // search range empty: not present
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11}; // MUST be sorted
    cout << binarySearch(arr, 6, 7) << endl; // 3
    cout << binarySearch(arr, 6, 4) << endl; // -1
    return 0;
}

For a million sorted elements, binary search needs only about 20 comparisons versus up to a million for linear search. That is the power of logarithmic growth.

The trade-off

The catch is the sorting cost. If you search an unsorted array just once, linear search wins — sorting first (O(n log n)) plus a binary search costs more than a single O(n) scan. But if you search the same sorted array many times, you sort once and enjoy O(log n) lookups forever after. Binary search is also the idea behind the binary search tree, which keeps data sorted as it changes.

When to use which

Use linear search for small arrays, one-off searches, or data that cannot be sorted (or is not). Use binary search when the data is already sorted, or when you will search it repeatedly enough to justify sorting once. For frequent lookups with no ordering need, a hash table gives average O(1) and beats both.

Common mistakes

• Binary searching unsorted data. Binary search silently returns wrong results on unsorted input. The sorted precondition is mandatory.
• Computing mid as (low + high) / 2. For large indices this can overflow. Use low + (high - low) / 2.
• Wrong loop condition. The loop must continue while low <= high. Using < skips the final single-element check and misses matches.
• Forgetting to move past mid. Set low = mid + 1 or high = mid - 1, not low = mid/high = mid, or the loop can spin forever.
• Sorting just to search once. If you only search an unsorted array a single time, a plain linear scan is cheaper than sorting plus binary search.

FAQ

Is binary search always better? Only on sorted data. On unsorted data you would have to sort first (O(n log n)), so for a single search linear is cheaper. Binary search pays off with repeated searches.

What if I need fast lookups but no ordering? A hash table gives average O(1) lookups and beats both search methods when you do not need sorted order.

Keep learning

Ground the speed comparison in Big-O Notation, see binary search applied to a dynamic structure in Binary Search Trees, and browse the full DSA hub.

Want to practise search algorithms with instructor feedback in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.