BINARY SEARCH ALGORITHM

 

A binary search is a simplistic algorithm intended for finding the location of an item stored in a sorted list. There are a few variations to the binary search in C program, such as testing for equality and less-than at each step of the algorithm.

How Does it Work?

Binary search algorithm applies to a sorted array for searching an element. The search starts with comparing the target element with the middle element of the array. If value matches then the position of the element is returned.

In case the target element is less than the middle element (considering the array follows an ascending order) of the array then the second half of the array is discarded and the search continues by dividing the first half.

The process is the same when the target element is greater than the middle element, only, in this case, the first half of the array is discarded before continuing with the search. The iteration repeats until a match for the target element is found.

Binary Search in C Program

The following code implements binary search in C programming language. Although it can only be used for sorted arrays, it is fast in comparison to the linear search.

If the requirements ask for using binary search on an unsorted array, then it needs to be sorted first before using the binary search algorithm on it. For doing so, you can make use of some sorting technique, such as the bubble sort or the merge sort , Quick Sort , Bubble Sort .

NOTE: - The code mentioned below assumes that the input numbers follow an ascending order!

Here goes the code for Binary Search in C:

#include 

int main()

{

   int c, first, last, middle, n, search, array[100];

   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 the value to find:\n");

   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("%d is present at index %d.\n", search, middle+1);

         break;

      }

      else

         last = middle - 1;

      middle = (first + last)/2;

   }

   if (first > last)

      printf("Not found! %d is not present in the list.\n", search);

   return 0;  

}

Sample Output:

Enter number of elements:

5

Enter 5 integers:

1

9

22

24

46

Enter the value to find:

24

24 is present at index 4.