C DSA Searching

Linear Search

Linear search is the simplest way to find a value. Check each item, one by one, from the start. Stop when you find the value, or when you reach the end.

It is like looking for your keys by checking every pocket, one after another.

Here is a linear search in C, where we search for the value 7:

#include <stdio.h>

// Returns the index of the value, or -1 if it is not found
int linearSearch(int arr[], int length, int value) {
  for (int i = 0; i < length; i++) {
    if (arr[i] == value) {
      return i;
    }
  }
  return -1;
}

int main() {
  int numbers[] = {4, 9, 2, 7, 5, 8};
  int length = sizeof(numbers) / sizeof(numbers[0]);

  int index = linearSearch(numbers, length, 7);

  if (index != -1) {
    printf("Found 7 at index %d\n", index);
  } else {
    printf("7 was not found\n");
  }

  return 0;
}

Found 7 at index 3

Run the simulation below to see how the code above works. Each column is one value in the array. The dashed line shows the value we search for (7): a column that reaches exactly up to the line has that value.

When you run the simulation, the yellow column is the one being checked. Grey columns did not match. If the value is found, its column turns green.

Linear search works on any array, sorted or not. But it can be slow. If the array has 1,000,000 items, you might have to check all 1,000,000 of them!

Binary Search

Binary search is much faster, but it only works on a sorted array. Here is how it works:

1. Look at the item in the middle.
2. If it is the value you want, you are done!
3. If the value you want is bigger, search only the right half. If it is smaller, search only the left half.
4. Repeat with the half that is left.

Every step throws away half of the items. Here we search for 23. The middle item is yellow, and grey items are already thrown away:

Three steps, and we found it!

Run the simulation below. It uses the same sorted array as the picture, and searches for 23 again. The value axis lists the values in the array, so you can see exactly what each column holds:

Watch the grey part grow: every check throws away half of the columns that are left. That is why binary search is so fast.

Here is binary search in C. It prints every item it checks:

#include <stdio.h>

// Returns the index of the value, or -1 if it is not found
int binarySearch(int arr[], int length, int value) {
  int low = 0;
  int high = length - 1;

  while (low <= high) {
    int middle = (low + high) / 2;
    printf("Checking index %d (value %d)\n", middle, arr[middle]);

    if (arr[middle] == value) {
      return middle;     // Found it
    } else if (arr[middle] < value) {
      low = middle + 1;  // Search the right half
    } else {
      high = middle - 1; // Search the left half
    }
  }

  return -1; // Not found
}

int main() {
  int numbers[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
  int length = sizeof(numbers) / sizeof(numbers[0]);

  int index = binarySearch(numbers, length, 23);

  if (index != -1) {
    printf("Found 23 at index %d\n", index);
  } else {
    printf("23 was not found\n");
  }

  return 0;
}

Checking index 4 (value 16)
Checking index 7 (value 56)
Checking index 5 (value 23)
Found 23 at index 5

Example Explained

• low and high mark the part of the array we still search. At the start, that is the whole array.
• middle is the index in the middle of that part.
• If the middle value is too small, we move low past the middle. If it is too big, we move high before the middle.
• When low becomes bigger than high, there is nothing left to search, so the value is not in the array.

Linear Search vs. Binary Search

How many checks does each search need in the worst case?

Binary search is amazingly fast. Even with a million items, it needs only 20 checks!

And now the answer to the guessing game: the smartest first guess is 50, right in the middle. Then keep guessing the middle of what is left. That is binary search, and you will always find the number in 7 guesses or fewer.

Summary

• Linear search checks every item, one by one. It works on any array.
• Binary search checks the middle item and throws away half of the items at every step.
• Binary search is much faster, but the array must be sorted.

Binary search needs sorted data. So how do you sort an array? That is the next chapter!