C program for binary search (recursive and iterative)

Binary search algorithm is an algorithm based on comparison and segmentation mechanism. The binary search algorithm is also called half-interval search, logarithmic search or binary search. Binary search algorithm to find the position of a target value in a sorted array. It compares the target value to the middle element of the array. If the element is equal to the target element, the algorithm returns the index of the found element. If they are not equal, the search algorithm uses half of the array, depending on the comparison of the values, the algorithm uses the first half (when the value is less than the middle) and the second half (when the value is less than the middle) and the second half (when the value is greater than the middle) . Do the same with the next half of the array.

Input:
A[] = {0,2,6,11,12,18,34,45,55,99}
n=55
Output:
55 at Index = 8

Explanation

For our array -

we will compare 55 with the middle element of the array 18, it is less than 55 so we will use the array The second half of the array is {24, 45, 55, 99}, and there is also 55 in the middle. Use it to check the value of the search element. And the matched value, then we will return the index of the value as 8.

If the search element is smaller than the middle, then we will use the first half and continue until the element is found in the middle of the array.

In order to implement binary search, we can write code in two ways. These two ways only differ from the way we call the function that checks the binary search element. They are:

• Use iteration - This means using a loop inside a function to check the equality of intermediate elements. < /p>

• Usage In this method, the function calls itself again and again with a different set of values.

Example

#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
   int A[] = {0,12,6,12,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d </p><p>",n,iterativeBsearch(A,10,n));
   return 0;
}
int iterativeBsearch(int A[], int size, int element) {
   int start = 0;
   int end = size-1;
   while(start<=end) {
      int mid = (start+end)/2;
      if( A[mid] == element) {
         return mid;
      } else if( element < A[mid] ) {
         end = mid-1;
      } else {
         start = mid+1;
      }
   }
   return -1;
}

Output

55 is found at Index 8

Example

#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
   if(start>end) return -1;
      int mid = (start+end)/2;
   if( A[mid] == element ) return mid;
   else if( element < A[mid] )
      RecursiveBsearch(A, start, mid-1, element);
   else
      RecursiveBsearch(A, mid+1, end, element);
}
int main() {
   int A[] = {0,2,6,11,12,18,34,45,55,99};
   int n=55;
   printf("%d is found at Index %d </p><p>",n,RecursiveBsearch(A,0,9,n));
   return 0;
}

Output

55 is found at Index 8

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