Searching in C: Linear Search and Binary Search

Searching means finding whether a target value exists in a collection of data, and if so, where. C (and every other language) commonly teaches two fundamental searching techniques: linear search and binary search. This is Post 1 of the Unit III series, opening with searching and sorting before moving to functions and recursion.

Linear Search

Linear search checks every element one by one, from the start, until it finds the target or reaches the end. It works on any array — sorted or not.

#include <stdio.h>

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;   // found — return its index
        }
    }
    return -1;   // not found
}

int main() {
    int arr[] = {23, 5, 67, 12, 89, 1};
    int n = 6, key = 12;

    int result = linearSearch(arr, n, key);

    if (result != -1) {
        printf("Element %d found at index %d.\n", key, result);
    } else {
        printf("Element %d not found.\n", key);
    }

    return 0;
}

Sample Output

Element 12 found at index 3.

Time Complexity

In the worst case (target is the last element, or absent entirely), linear search checks every one of the n elements — this is written as O(n) time complexity. Simple, but slow for large datasets.

Binary Search

Binary search is dramatically faster — but has one requirement: the array must already be sorted. It works by repeatedly checking the middle element and eliminating half the remaining search space each time.

#include <stdio.h>

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            low = mid + 1;    // key must be in the right half
        } else {
            high = mid - 1;   // key must be in the left half
        }
    }

    return -1;   // not found
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};   // MUST be sorted
    int n = 10, key = 23;

    int result = binarySearch(arr, n, key);

    if (result != -1) {
        printf("Element %d found at index %d.\n", key, result);
    } else {
        printf("Element %d not found.\n", key);
    }

    return 0;
}

Sample Output

Element 23 found at index 5.

Tracing Binary Search for key = 23

Array (indices 0-9): 2  5  8  12  16  23  38  45  56  72

Step 1: low=0, high=9, mid=4 -> arr[4]=16. 16 < 23, so search right half: low = 5
Step 2: low=5, high=9, mid=7 -> arr[7]=45. 45 > 23, so search left half: high = 6
Step 3: low=5, high=6, mid=5 -> arr[5]=23. Match! Return index 5.

Time Complexity

Each step eliminates half the remaining elements, giving binary search a time complexity of O(log n) — for an array of 1 million sorted elements, binary search needs at most about 20 comparisons, versus up to 1 million for linear search in the worst case.

Linear Search vs. Binary Search

Summary

• Linear search checks every element in order; works on any array; O(n).
• Binary search repeatedly halves the search space; requires a sorted array; O(log n), far faster for large datasets.
• Choosing between them is a direct trade-off: if your data is already sorted (or sorted once and searched many times), binary search wins decisively; for small or unsorted one-off searches, linear search is simpler and perfectly adequate.

Further Reading

• Linear Search in a 1-D Array in C (worked lab example on this blog)
• Linear vs Binary Search + Code in C (video embedded above)
• GeeksforGeeks: Binary Search

Next in this series: sorting — bubble sort, selection sort, and insertion sort.