C Program for Binary Search

Problem:

Write a c program for binary search. Write a c program to implement binary search on an integer array to find an element in the array using function.

Solution:

Binary search algorithm is used in data structures as searching technique to find an element in given data. Its advantages are time complexity of binary search algorithm is O(log2n) which is very efficient and it does not require any additional data structure.

Here we are going to implement binary search algorithm in C programming language. Binary searching technique is only useful when data is in sorted manner. Binary search algorithm is comparatively faster than linear search algorithm. Both work on sorted data. If we want to use binary search technique on unsorted data then we first have to sort the data using any sorting technique such as bubble sort, insertion sort, merge sort or quick sort.

In this program we are going to accept array elements from user and then we are going to sort the array using bubble sort because it is comparatively simpler than others and then we are going to search an element in the sorted array using binary search and print its position in the array.

Algorithm:

Here is the algorithm of C program for binary search
  1. Start
  2. Accept the value be searched in an array (say) as key
  3. Declare and initialize top=0
  4. Declare and initialize bottom=size-1, where size is the size of the array.
  5. mid=(top+bottom)/2
  6. If arr[mid]==key
    • Display record found at position mid
    • goto 10
  7. If key<arr[mid]
    • bottom=mid-1
    • else
    • top=mid+1
  8. If top<=bottom
    • goto 5
  9. Display record not found
  10. Stop

C program for binary search:

Here is the source code of C program for binary search 
/* Aim: Write a c program for binary search */

#include<stdio.h>

// Binary_Search() function to implement binary search
int Binary_Search(int arr[],int key, int size)
{
	int top=0,mid,bottom=size-1;
 
	while(top<=bottom)
	{
	mid=(top+bottom)/2;
  
	if(arr[mid]==key)
		return mid+1;
	else
		if(key<arr[mid])
			bottom=mid-1;
		else
			top=mid+1;
	}
 
	return -1;
}

void Bubble_Sort(int arr[],int size)
{
	int i,j,tmp;

	for(i=1;i<size;i++)
		for(j=0;j<size-i-1;i++)
		{
			if(arr[i]>arr[i+1])
			{
			tmp=arr[i];
			arr[i]=arr[i+1];
			arr[i+1]=tmp;
			}
		}
}

int main()
{
 int i,size,key,pos,arr[100];

 printf("\n How many elements to accept:- ");
 scanf("%d",&size);

 printf("\n Enter the elements:- ");
 for(i=0;i<size;i++)
  scanf("%d",&arr[i]);
 
 Bubble_Sort(arr,size);

 printf("\n Enter the element to be searched in the array:- ");
 scanf("%d",&key);

 pos=Binary_Search(arr,key,size);

 if(pos==-1)
  printf("\n Element is not present in the array. \n");
 else 
  printf("\n Element found at position %d",pos);

 return 0;
}

/* Output of above code / Runtime test cases:

 How many elements to accept:- 5

 Enter the elements:- 99 95 98 99 100

 Enter the element to be searched in the array:- 100

 Element found at position 5

*/

Labels:











Labels