Unit 5 · Lesson 420 minAcademic review pending

Two ways to look, one far faster

Linear search checks every element; binary search halves the range each step but demands a sorted array. The difference grows enormous with size.

Choose explanation

After this lesson

You should be able to

Implement both linear and binary search.
State the precondition binary search requires.
Compare the two by counting comparisons rather than by timing.

Linear search: simple and always correct

Check each element until you find the target or run out. It needs no preparation and works on any array in any order. On average it looks at half the elements, and in the worst case all of them.

For a few dozen items that is entirely fine. The reason to learn something better is that arrays get large, not that linear search is wrong.

Binary search: halve the range

Look at the middle element. If it is the target, stop. If the target is smaller, everything to the right is irrelevant, so discard it; if larger, discard the left. Each comparison removes half the remaining elements.

In 1,000 elements linear search may take 1,000 comparisons; binary search takes at most about 10, because 2 to the power 10 exceeds 1,000. At a million elements it is about 20 against a million. That gap is the entire reason sorting is worth its cost.

The range shrinks by half every pass

int binary_search(const int data[], int n, int target)
{
    int low = 0, high = n - 1;

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

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

    return -1;
}

The precondition is not optional

Binary search only works on a sorted array. On unsorted data it does not report an error — it discards the half containing your target and confidently returns not found. That silent wrong answer is worse than a slow one.

So sorting is an investment: costly once, then every later search is cheap. Sort once and search a thousand times and it pays for itself many times over; sort to make one search and you have lost.

Try it yourself

Search a sorted array of ten marks with both methods and count how many comparisons each one makes.

Need a hint?

Pass a pointer to a counter and increment it inside each loop.

Check the worked solution

Counting comparisons rather than timing is the honest measure — it does not depend on the machine or on what else is running. For a worst-case target linear search makes ten comparisons and binary search four, and the gap widens as the array grows: at 1,000 elements it is 1,000 against 10.

#include <stdio.h>
#define SIZE 10

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

int binary_search(const int a[], int n, int target, int *steps)
{
    int low = 0, high = n - 1;

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

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

int main(void)
{
    int marks[SIZE] = {12, 25, 31, 44, 50, 63, 71, 88, 92, 99};
    int ls = 0, bs = 0, target = 99;

    printf("linear: index %d in %d comparisons\n",
           linear_search(marks, SIZE, target, &ls), ls);
    printf("binary: index %d in %d comparisons\n",
           binary_search(marks, SIZE, target, &bs), bs);

    return 0;
}

Quick check

What happens if you run binary search on an unsorted array?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

Basic searching in an array of elements (linear and binary search techniques)

Maps to course outcome CO6.