Implementation of binary search (recursive and iterative) in C program

Binary search is a search algorithm used to find the position of an element (target value) in a sorted array. The array should be sorted before applying binary search.

Binary search is also called logarithmic search, binary search, and semi-interval search.

Working Principle

The binary search algorithm works by comparing the element to be searched with the middle element of the array, and performs the required process based on the result of this comparison.

Case 1 - element = middle value, find the element and return the index.

Case 2 - element > middle value, searches for an element in the subarray indexed from middle 1 to n.

Case 3 - element

Algorithm

Initial parameter value, end value

Step 1 : Find the middle element of array. using ,
middle = initial_value + end_value / 2 ;
Step 2 : If middle = element, return ‘element found’ and index.
Step 3 : if middle > element, call the function with end_value = middle - 1 .
Step 4 : if middle < element, call the function with start_value = middle + 1 .
Step 5 : exit.

The implementation function of the binary search algorithm uses repeated calling functions. This call can be of two types:

• Iteration
• Recursion

Iteration callis looping the same piece of code multiple times.

Recursive call is to call the same function repeatedly.

A program that uses iterative calls to implement binary search

Example

Demonstration

#include <stdio.h>
int iterativeBinarySearch(int array[], int start_index, int end_index, int element){
   while (start_index <= end_index){
      int middle = start_index + (end_index- start_index )/2;
      if (array[middle] == element)
         return middle;
      if (array[middle] < element)
         start_index = middle + 1;
      else
         end_index = middle - 1;
   }
   return -1;
}
int main(void){
   int array[] = {1, 4, 7, 9, 16, 56, 70};
   int n = 7;
   int element = 16;
   int found_index = iterativeBinarySearch(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;
}

Output

Element found at index : 4

Uses recursive calls to implement binary search Program

Example

Online demonstration

#include <stdio.h>
int recursiveBinarySearch(int array[], int start_index, int end_index, int element){
   if (end_index >= start_index){
      int middle = start_index + (end_index - start_index )/2;
      if (array[middle] == element)
         return middle;
      if (array[middle] > element)
         return recursiveBinarySearch(array, start_index, middle-1, element);
      return recursiveBinarySearch(array, middle+1, end_index, element);
   }
   return -1;
}
int main(void){
   int array[] = {1, 4, 7, 9, 16, 56, 70};
   int n = 7;
   int element = 9;
   int found_index = recursiveBinarySearch(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;
}

Output

Element found at index : 3

The above is the detailed content of Implementation of binary search (recursive and iterative) in C program. For more information, please follow other related articles on the PHP Chinese website!