Searching Algorithms in C

Analogy categoryAnalogies

1. Introduction

Searching is the process of finding whether a target value exists within a data structure, and if so, at what position. In C, the two fundamental searching algorithms are linear search, which checks every element one by one, and binary search, which repeatedly halves a sorted array to locate the target much faster. Choosing the right algorithm depends on whether the data is sorted and how large the dataset is.

🏏

Cricket analogy: Searching for a player's score is like scanning every entry on a paper scoresheet one by one (linear search) versus flipping straight to the middle of an alphabetically sorted squad list (binary search) to halve your options fast.

Linear search works on any array, sorted or not, and is simple to implement, but it scales poorly for large datasets. Binary search is dramatically faster but requires the array to already be sorted — if it isn't, you must sort it first (see the dedicated sorting lessons), which adds its own cost.

🏏

Cricket analogy: Linear search is like checking every player's stats on an unsorted team sheet, which works but is slow, while binary search demands the sheet be sorted by, say, batting average first, adding the extra work of sorting.

2. Syntax

int linearSearch(int arr[], int n, int key);
int binarySearch(int arr[], int n, int key);

Both functions take an array, its size, and the key to search for, and conventionally return the index of the key if found, or -1 if not found. binarySearch assumes 'arr' is already sorted in ascending order; linearSearch makes no such assumption.

🏏

Cricket analogy: Both search functions take a squad list, its size, and a player's name to find, returning the batting position if found or -1 if absent; binarySearch assumes the squad is sorted by name, linearSearch makes no such assumption.

3. Explanation

Linear search iterates through the array from index 0 to n-1, comparing each element to the key. If a match is found, it returns that index immediately; if the loop finishes without a match, it returns -1. This works regardless of order but requires up to n comparisons in the worst case, giving it O(n) time complexity.

🏏

Cricket analogy: Linear search is like a scout reading every name on an unsorted squad list from top to bottom until finding the target player, stopping immediately on a match but checking all names in the worst case — O(n).

Binary search only works on a sorted array. It maintains 'low' and 'high' bounds, computes a middle index 'mid', and compares arr[mid] to the key. If they match, the search is done. If the key is smaller, the search continues in the left half (high = mid - 1); if larger, it continues in the right half (low = mid + 1). Because each comparison eliminates half the remaining elements, binary search runs in O(log n) time — dramatically faster than linear search for large sorted datasets.

🏏

Cricket analogy: Binary search is like flipping straight to the middle page of an alphabetically sorted squad directory, checking that name against the target, then discarding the irrelevant half and repeating — halving the search each time for O(log n).

Binary search gives incorrect results (or fails to find an existing element) if the array is not sorted first. Also watch for the classic overflow bug: computing mid as (low + high) / 2 can overflow for very large low+high on some systems; the safer form is mid = low + (high - low) / 2.

Time complexity comparison: linear search is O(n) — works on unsorted data but scales linearly. Binary search is O(log n) — requires sorted data but scales logarithmically, meaning it can search a million-element sorted array in about 20 comparisons versus up to a million for linear search.

4. Example

#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 at index i */
        }
    }
    return -1; /* not found */
}

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; /* avoids overflow */
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1; /* not found */
}

int main(void) {
    int unsorted[] = {42, 7, 19, 3, 88};
    int sorted[]   = {3, 7, 19, 42, 88};
    int n = 5;

    int idx1 = linearSearch(unsorted, n, 19);
    printf("Linear search for 19: index %d\n", idx1);

    int idx2 = binarySearch(sorted, n, 19);
    printf("Binary search for 19: index %d\n", idx2);

    int idx3 = binarySearch(sorted, n, 100);
    printf("Binary search for 100: index %d\n", idx3);

    return 0;
}

5. Output

text

Linear search for 19: index 2
Binary search for 19: index 2
Binary search for 100: index -1

6. Key Takeaways

Linear search checks each element in order and works on unsorted or sorted data in O(n) time.
Binary search requires a sorted array and repeatedly halves the search range, running in O(log n) time.
Binary search compares arr[mid] to the key and moves low or high accordingly.
Use mid = low + (high - low) / 2 to avoid potential integer overflow.
A dedicated Binary Search topic covers recursive variants and edge cases in more depth.