C program to search for a element in an array using binary search algorithm

      A binary search or half-interval search algorithm locates the position of an item in a sorted array. In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special “not found” indication is returned. Binary search algorithm typically halve the number of items to check with each successive iteration, thus locating the given item (or determining its absence) in logarithmic time. A binary search is a divide and conquer search algorithm.

binary search program in c



Source Code :

#include<stdio.h>
int binarysearch(int a[], int n, int key)
{
    int beg,mid,end;
    beg=0; end=n-1;
    
    while( beg < = end )               //Step3
    {
       mid=(beg+end)/2;         // Step 3(i)
	    if(key==a[mid])
            return mid;         // Step 3(ii)
        else if(key>a[mid])     //Step 3(iii)
            beg=mid+1;
		else
			end=mid-1;      //Step 3(iv)
    }
   return -1;
    
}
 
int main()
{
    int arr[50], n, key, index;
 
    printf("How many elements do you want to create the array with?(max 50): ");
    fflush(stdout);
 
    scanf("%d", &n);
 
    puts("Enter the array elements in ascending order");
    for (index = 0; index < n; index++)
        scanf("%d", &arr[index]);                    //Step1 
    printf("Enter the search key: ");           
    fflush(stdout);
 
    scanf("%d", &key);                            // Step 1
 
    index = binarysearch(arr, n, key);             // Step 2
 
    if (index == -1)
        puts("Sorry, the given key was not found");
    else
        printf("The given key was found at index: %d\n", index);   //Step4
 
    return 0;
}


edit-code-image

Sample Test cases:

1. How many elements do you want to create the array with?(max 50): 5
   Enter the array elements in ascending order
   1
   56
   63 
   89
   100
   Enter the search key: 56
   The given key was found at index: 1

2.How many elements do you want to create the array with?(max 50): 4
  Enter the array elements in ascending order
  34
  67
  89
  121
  Enter the search key: 4
  Sorry, the given key was not found

Explanation:

Step 1 : The array and the key are read from the user using scanf() function.

Step 2 : The binary_search function is called from the main program.

Step 3 : The loop iterates until key found at the middle or until all elements are finished.

Step 3(i) : The index of middle element is calculated from the index of first(i.e.,beg) and last
element(i.e.,end-1).

Step 3(ii) : The middle element is checked against key. If both are equal then it implies that key
is found and function retruns the index of middle element.

Step 3(iii): If key value is greater than middle element then search has to be performed in right
part of the array. So beg is made as middle element index.

Step 3(iv) : Otherwise the search has to be performed in left part of the array. So end is made as
middle element index.

Step 4 : Finally the corresponding output from the function is printed on the output screen
using printf() function.

More Insights:

Algorithm

Algorithm working explanation.

Explore C Programs:C Programs