C program for Binary search algorithm

C program for Binary search algorithm

1097
6
SHARE

C program for binary search algorithm : Binary search is a searching algorithm which searches an element in the sorted list. In each step,binary search algorithm compares the input number(to be searched) with the value of the middle element of the array. If the values match, then a matching element has been found so its index, or position, is returned. Otherwise, if the searched number is less than the middle element’s value, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input number is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the number cannot be found in the array then a special “Not found” indication is returned. Let us see a basic implementation of binary search algorithm using iterations.

int binary_search(int A[], int key, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imax >= imin)
    {
      /* calculate the midpoint for roughly equal partition */
      int imid = midpoint(imin, imax);

      // determine which subarray to search
      if      (A[imid] <  key)
        // change min index to search upper subarray
        imin = imid + 1;
      else if (A[imid] > key )
        // change max index to search lower subarray
        imax = imid - 1;
      else
        // key found at index imid
        return imid;
  }
  // key not found
  return KEY_NOT_FOUND;
}

The above code is just an snippet to see how the binary search algorithm works. Now lets see the complete algorithm.

Note : The input list should be in sorted order (ascending order) else program will not work as expected. If you want to provide the unsorted list of elements as input then first of all you need to sort the elements and then do the binary search.

Have a look at different sorting programs:

C program of Bubble Sort Algorithm

C program for Selection Sort Algorithm

C program of Merge Sort Algorithm

Now lets see complete C code of binary search algorithm.

C program for Binary search algorithm using iterations :

#include<stdio.h>
#include<conio.h> 
main()
{
   int c, first, last, middle, n, search, array[100];
   printf("***************************************************\n");
   printf("**************written by Ccodechamp****************\n");
   printf("***************************************************\n\n\n");
   printf("Enter number of elements: ");
   scanf("%d",&n);

   printf("\nEnter %d integers in sorted sorted :\n", n);

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

   printf("\nEnter value to be searched in above list : ");
   scanf("%d",&search);

   first = 0;
   last = n - 1;
   middle = (first+last)/2;

   while( first <= last )
   {
      if ( array[middle] < search )
         first = middle + 1;    
      else if ( array[middle] == search ) 
      {
         printf("\n%d found at position %d.\n", search, middle+1);
         getch();
         break;
      }
      else
         last = middle - 1;

      middle = (first + last)/2;
   }
   if ( first > last )
      printf("Not found! %d is not present in the above list.\n", search);
      getch();

   return 0;   
}

 

We hope that you all like the above . If you have any queries regarding the logic ask us in form of comments.

6 COMMENTS

  1. I simply want to tell you that I’m newbie to blogs and seriously enjoyed you’re web blog. Almost certainly I’m want to bookmark your blog . You amazingly come with very good posts. With thanks for sharing with us your web page.

    • Hello, I wish for to subscribe for this web site to obtain latest updates, thus where can i do it please assist.

  2. I was suggested this web site by way of my cousin. I am now not certain whether or not this publish is written through him as nobody else understand such detailed about my difficulty. You are amazing! Thanks!

  3. Thanks for every other informative website. Where else may just
    I am getting that type of information written in such
    a perfect means? I’ve a mission that I am just now working on, and
    I’ve been at the look out for such info.

LEAVE A REPLY