Binary Search in C

In this tutorial, We will learn Binary Search in C with practical implementation. A binary search (also known as half-interval search or logarithmic search) is similar to a linear search, but It’s a technique that is faster than a linear search except for small arrays. Binary search implemented only for sorted array or list. If the array elements not sorted, we need to sort them first.

What is Binary Search in C?

Binary Search: The binary search algorithm uses divide and conquer method. It is a search algorithm used to find an element position in the sorted array. It is useful when there is a large number of elements in an array. Binary search algorithm can be applied on sorted binary trees, sorted linear array, pointer array.

The binary search begins by comparing the searched element with the middle element of the array. Since ‘mid’ calculate for every iteration or recursion, we divide the array into half and then try to solve the problem. If the searched value is less than the element in the middle of the array, then search continued in the lower half. Otherwise, the search continued in the upper half. We were repeating this process until the element found, or there no more array element left to search.

For example: 2,5,8,12,16,23,38,56,72,91,97.

The following steps will follow to find an element 38 with a binary search in the array.

The middle element of the array is selected as 23 and compared with the searched element 38. The searched element (38) is not equal to the middle element (23), of the array, which is greater than 23, So search is continued in the upper half.

Our new search array(Upper half of array): 38,56,72,91,97.

The middle element of our new search array is 72, which is greater than searched element 38,

So, Our new search array: 38,56

And then a search is completed.

Binary Search Time Complexity

To determine the complexity of the binary search algorithm, we need to know the number of comparisons made to search the ITEM in the array A containing N elements in sorted order.

The best-case occurs if the middle element is equal to the item to search. In that case, the loop executes only 1 time, and in Big-O notation, the complexity can express as O(1).

The worst case occurs if the item we are looking for is not in the array. In that case, the number of comparisons made will be the number of times the loop iterates. On each iteration, the size of the array is reduced by half before the size of the array reaches or goes below 1 (i.e., only l item to check) as we know from algorithm complexity that whenever loop size is cut to half, then, in that case, Big-O notation is expressed as log₂n. Therefore, in our case, complexity is defined as O (log₂n).

In the worst-case scenario, searching an array contain 1024 elements will take only 10 comparisons (log₂ I024 = 10). Similarly, an array containing 2²⁰ elements will require 20 comparisons in the worst case to locate the search item. Thus, using binary search, there is a tremendous increase in performance over linear search that requires 2²⁰ comparisons to search an item in an array containing 2²⁰ elements.

Binary Search Algorithm

Step 1 : Find the centre element of array.
         centre = first_index + last_index / 2 ;
Step 2 : If centre = element, return 'element found' and index.
Step 3 : if centre > element, call the function with last_index = centre - 1 .
Step 4 : if centre < element, call the function with first_index = centre + 1 .
Step 5 : exit.

Binary Search Program Using Iterative

Let us implement an example with binary search program,

#include <stdio.h>
int BinarySearch(int array[], int first_index, int last_index, int element){
 while (first_index <= last_index){
  int centre = first_index + (last_index - first_index )/2;
  if (array[centre] == element)
     return centre;
    if (array[centre] < element)
      first_index = centre + 1;
    else
      last_index = centre - 1;
 }
 return -1;
}
int main(void){
  int array[] = {2,5,8,12,16,23,38,56,72,91,97};
  int n = 11;
  int element = 38;
  int found_index = BinarySearch(array, 0, n-1, element);
  if(found_index == -1 ) {
    printf("Element not found in the array ");
  }
  else {
   printf("Element found at index : %d",found_index);
  }
  return 0;
}

Binary Search Program Using Recursive Method

#include<stdio.h>
int BinarySearch(int array[], int first_index, int last_index, int element){
  if (last_index >= first_index){
    int centre = first_index + (last_index - first_index )/2;
    if (array[centre] == element)
       return centre;
       if (array[centre] > element)
         return BinarySearch(array, first_index, centre-1, element);
         return BinarySearch(array, centre+1, last_index, element);
  }
  return -1;
}
int main(void){
  int array[] = {2,5,8,12,16,23,38,56,72,91,97};
  int n = 11;
  int element = 38;
  int found_index = BinarySearch(array, 0, n-1, element);
  if(found_index == -1 ) {
    printf("Element not found in the array ");
  }
  else {
    printf("Element found at index : %d",found_index);
  }
  return 0;
}