Searching: linear and binary

Two ways to search

• Searching means finding where a value is in an array (or saying it is not there).
• Linear search checks every item one by one. It works on any array.
• Binary search is much faster but needs the array to be sorted first.

Linear search

• Walk from index 0 to n - 1, comparing each item to the target.
• Return the index the moment you find it. If you reach the end, return -1.
• For an array of n items, this looks at up to n of them.

Why sorting enables binary search

• If the array is sorted, you can jump to the middle and compare.
• If the middle is too small, the target must be in the right half; if too big, the left half.
• Each step throws away half the array, so it is very fast (about log2(n) steps).

low, high, mid

• Keep two bounds: low (start) and high (end). The middle is mid = low + (high - low) / 2.
• If a[mid] is the target, return mid. If a[mid] < target, move low = mid + 1; else high = mid - 1.
• Stop when low > high — the target is not there, so return -1.

#include <stdio.h>

int main(void) {
    int a[] = {1, 3, 5, 7, 9};   // sorted!
    int target = 7, lo = 0, hi = 4, found = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) { found = mid; break; }
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    printf("%d\n", found);   // 3
    return 0;
}

Common mistakes

• Binary search needs a sorted array.
• Linear search checks each element in turn.

Now you try

• For binary search, assume the array is already sorted. Use low, high, and mid.
• Return -1 when the value is not found. Do not write a main — the checker provides one.