Write a C program for Binary Search.

Algorithm
Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure
Figure: Binary Search
C Programming Code

#include <stdio.h>
int binarySearch(int [], int, int, int);

int main()
{
    //!showArray(array)
  int array[10], c, first, last, n, search,  index;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  printf("Enter value to find\n");
  scanf("%d", &search);

  first = 0;
  last = n - 1;

  index = binarySearch(array, first, last, search);
 
  if (index == -1)
    printf("Not found! %d isn't present in the list.\n", search);
  else
    printf("%d is present at location %d.\n", search, index + 1);
 
  return 0;
} 

int binarySearch(int a[], int s, int e, int f) {
  int m;
 
  if (s > e) // Not found
     return -1;

  m = (s + e)/2;

  if (a[m] == f)  // element found
    return m;
  else if (f > a[m])  
    return binarySearch(a, m+1, e, f);
  else
    return binarySearch(a, s, m-1, f);
}

Output

Enter number of elements
5
Enter 5 integers
1
2
3
4
5
Enter value to find
5
5 is present at location 5.

Unknown's avatar

Published by Md. Anisur Rahman

I am Md. Anisur Rahman. I have completed Cyber Security for MSCSE at United International University in 2022.I have completed PGDIT from IIT, Jahangirnagar University in 2020. I'm a Head of IT at Programming24 School.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.