Programming: Search

Search

Linear Search: O(N)

It’s the simplest search algorithm, a sequential approach to find an element in a list.

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

If the array is sorted could improve the algorithm by using jumps of k elements, instead of 1. This way, we can reduce the number of comparisons in the worst case from n to n/k. Let’s say 10%:

The number of comparations is n/k + k-1. For 10 jumps, the worst case is to search for the highest number (9+0.1N) -> O(N) but better than linear search.

Binary Search: O(lg N)

In an sorted array, what if we keep junping by 50%?

We set a left and right index, and we calculate the middle point. If the value is greater than the middle point, we set the left index to the middle point. If the value is less than the middle point, we set the right index to the middle point. We repeat this process until we find the value.

So it’s doing N/2, N/4,... until it searches until N/2^k = 1 => k = lg N

If it halves at each step, it’s likely O(lg N) or O(N lg N).

Code:

int binarySearch(int arr[], int rg, int x) {
  int m, lf = 0;

  while (lf <= rg) {
    m = lf + (rg - lf) / 2;
    // If x is smaller, ignore right half
    if (arr[m] < x)
      lf = m + 1;
    // If x greater, ignore left half
    else if (arr[m] > x)
      rg = m - 1;
    // Check if x is present at mid
    else
      return m;
  }
  return -1;
}

In case of duplicates, the algorithm can be changed to return the fileftmost or rightmost element.

• Worst-case performance: O(lg N)
• Best-case performance: O(1)
• Average performance: O(lg N)
• Worst-case space complexity: O(1)