Searching in C

When you store many values (e.g., in an array), you often need to **find whether a given value exists** — this process is called searching.

Different searching algorithms exist, each suited for different situations.

Linear search checks each element one-by-one from start to end until the target value is found.

Algorithm (Pseudo-code)

for i = 0 to n-1:
    if array[i] == target:
        return i
return -1

C Implementation

#include <stdio.h>

int linearSearch(int a[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (a[i] == target)
            return i;
    }
    return -1;
}

int main() {
    int a[] = {3, 5, 2, 9, 6};
    int n = 5;
    int target = 9;

    int idx = linearSearch(a, n, target);

    if (idx != -1)
        printf("Found at index %d", idx);
    else
        printf("Not found");

    return 0;
}

Time Complexity: O(n) — checks all elements in worst case.

Binary search works only on sorted arrays. It repeatedly divides the search space in half.

📌 Real Life Example: Checking CCTV Footage

Imagine you want to find the exact time when a bike was stolen using 12 hours of CCTV footage.

• You don’t start at the beginning.
• You skip to the **middle (6th hour)** and check if theft is before or after.
• If it happened after → look in hour 7–12
• Again go halfway → hour 9
• And so on…

This is EXACTLY how binary search works — **keep cutting the search space in half**.

Binary Search Algorithm

low = 0
high = n-1

while low ≤ high:
    mid = (low + high) / 2
    
    if array[mid] == target: return mid
    if array[mid] < target: low = mid + 1
    else: high = mid − 1

return -1

C Implementation

#include <stdio.h>

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

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

        if (a[mid] == target)
            return mid;
        else if (a[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1;
}

int main() {
    int a[] = {2, 4, 6, 8, 10};
    int n = 5;
    int target = 6;

    int idx = binarySearch(a, n, target);

    if (idx != -1)
        printf("Found at index %d", idx);
    else
        printf("Not found");

    return 0;
}

Time Complexity: O(log n) — extremely fast.

#include <stdio.h>

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

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

        if (a[mid] == target)
            return mid;
        else if (a[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

int main() {
    int n, target;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int a[n];

    printf("Enter %d sorted numbers: ", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    printf("Enter target value: ");
    scanf("%d", &target);

    int idx = binarySearch(a, n, target);

    if (idx != -1)
        printf("Found at index %d", idx);
    else
        printf("Not found");

    return 0;
}