Searching Algorithms

The purpose of sorting is to reorder data whereas the purpose of search is to find the desired data. Sorting thus serves to prepare a dataset for more efficient searching. Two basic search algorithms are:

• Linear or sequential search
• Binary

Linear/sequential search

This algorithm iterates through the entire list of items one by one until the data is found. It is a very naive searching algorithm as finding an element could require searching the entire list.

#include <stdio.h>

int linear_search(int *list, int key, int n) {
  for (int i = 0; i < n; i++) {
    if (list[i] == key) {
      return i;
    }
  }
  return -1;
}

int main() {
  int list[] = {1, 2, 45, -2, 13, 12};
  int key = 45;
  int n = sizeof(list) / sizeof(list[0]);
  int i = linear_search(list, key, n);
  if (i == -1) {
    printf("Did not find element\n");
    return -1;
  }
  printf("Found element %d at index %d\n", key, i);
  return 0;
}

Binary search

This requires the data to be sorted in either ascending or descending order. It is much faster than linear search but requires that the data be sorted first.

#include <stdio.h>

int main() { return 0; }