Home > Backend Development > C++ > Implementation of binary search (recursive and iterative) in C program

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

WBOY
Release: 2023-08-26 14:37:11
forward
961 people have browsed it

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.
Copy after login

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;
}
Copy after login

Output

Element found at index : 4
Copy after login

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;
}
Copy after login

Output

Element found at index : 3
Copy after login

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!

Related labels:
source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template