Binary search algorithm in C, Recursive, Iterative, examples

If you have a sorted array, binary search algorithm is the quickest way. In a sorted array or list, binary search is used to increase the speed of the search operation.

You might be wondering why we would want to arrange the array in that particular order? The benefit of structuring the array is that it greatly reduces the search time.

When compared to Linear Searching, Binary Searching is much faster because the binary search reduces the number of iterations .

Working of binary search

We can implement Binary Search Algorithm in two ways.

• Iterative Way
• Recursive Way

How does Binary Search Work? In binary search, we locate the key element by using the element that is nearly in the middle of the array. The search is successful if a match is found.

If we don’t find the element, we search for the main element in a similar manner, either in the top or bottom half of the array.

If array is in ascending order : The search will continue on the lower half of an array if the array is in ascending order and the key element is smaller than the middle element. The search will continue at the upper half of an array if the key element is greater than the middle element.

If array is in descending order : The search will continue on the lower half of an array if the array is in descending order and the key element is greater than the middle element. The search will continue at the upper half of an array if the key element is less than the middle element.

Program of Binary Search using iterative way

#include <stdio.h>

#define MAX 8
int main() {
  int array[MAX] = {
    10,
    20,
    30,
    36,
    50,
    60,
    65,
    80
  };
  int keyElement = 65;
  int first, last, middle;

  first = 0;
  last = MAX - 1;
  middle = (first + last) / 2;

  while (first <= last) {
    if (array[middle] < keyElement) {
      first = middle + 1;
    } else if (array[middle] == keyElement) {
      printf("%d is found at %d location.\n", keyElement, middle + 1);
      break;
    } else {
      last = middle - 1;
    }
    middle = (first + last) / 2;
  }
  if (first > last)
    printf("%d is not available in the array.\n", keyElement);

  return 0;
}

Output:
65 is found at 7 location.

Program of Binary Search using recursive way

#include <stdio.h>

#define MAX 8
int main() {
  int array[MAX] = {
    10,
    20,
    30,
    36,
    50,
    60,
    65,
    80
  };
  int keyElement = 36;
  int first, last, middle, index;

  first = 0;
  last = MAX - 1;

  index = binarySearch(array, keyElement, first, last);
 
  if (index == -1) {
    printf("%d is not available in the array.\n", keyElement);
  }
  else {
   printf("%d is found at %d location.\n", keyElement, index + 1);
  }
  return 0;
}

int binarySearch(int array[], int keyElement, int first, int last) {
  if (last >= first) {
    int mid = first + (last - first) / 2;

    // If found at mid, then return it
    if (array[mid] == keyElement)
      return mid;

    // Search the first half
    if (array[mid] > keyElement)
      return binarySearch(array, keyElement, first, mid - 1);

    // Search the second half
    return binarySearch(array, keyElement, first + 1, last);
  }

  return -1;
}

Output:
36 is found at 4 location.

Also Read: Bubble Sort in Data Structure

Time Complexities of Binary Search

In binary search, the number of comparisons will be needed to find an search element in a array or list will not more than O(log n), where n is the number of elements in the list or array. As a result, the binary search technique has a time complexity of O(n *(log n).

• Worst case complexity: O(log n)
• Average case complexity: O(log n)
• Best case complexity: O(1)

Space Complexity of Binary Search

The space complexity of a binary search algorithm is affected by how the algorithm is implemented. The space complexity in the iterative technique will be O(1) and in the recursive technique will be O(log n).

Advantages of Binary Search Algorithm

• Because binary search indicates whether to look for an element before or after the current place, it eliminates half of the array from the search by comparing the results.
• Binary Search performs much better than linear search for large data sets.

Disadvantages of Binary Search Algorithm

• It’s difficult to create a binary search program since it’s prone to errors.
• Because of its random access nature, binary search has a poor memory interaction.
• More stack space is required for the recursive technique.