Implementation of Binary Search in C

PROBLEM STATEMENT

Write a C program to implement Binary Search Algorithm.

Include a function

int BinarySearch (int, int, int *, int x) --- The 1st parameter is the lower limit of the list or array, the 2nd parameter is the upper limit of the list or array, the third parameter is a pointer to the array and the fourth parameter is the search element.

Please note that the index of the search element is returned by the function. If the search element is not present in the array, -1 is returned.

Assume that the maximum size of the array is 10 . Please note that if a is the array, then a[0] is in position 0, a[1] is in position 1 ...

Input and Output Format:

Refer sample input and output for formatting specifications.

Sample Input and Output 1:

[All text in bold corresponds to input and the rest corresponds to output.]

Enter the number of elements :
5
Enter the elements :
12
16
23
45
67
Enter the element to be searched :
23
The element 23 is in position 2

Sample Input and Output 2:

[All text in bold corresponds to input and the rest corresponds to output.]

Enter the number of elements :
5
Enter the elements :
12
16
23
45
67
Enter the element to be searched :
28
The element 28 is not present in the array

SOLUTION

Here is the program to solve, if you don't understand any part, feel free to ask in comments.

	#include <stdio.h>
	#include <stdlib.h>
	//first we will declare required function
	int BinarySearch(int first,int last, int *arr,int x){
	int mid;
	//if fist > last, whole list is traversed and element is not found
	while(first<=last){
	mid=(first+last)/2;
	//if search element is mid element, we found our element !! return the position and terminate this function
	if(x==arr[mid])
	return mid;
	//if element is less than middle element, we need to shrink th list
	//now, list will be half. first=0 and last will be one element previous of middle, so last=middle-1
	else if(x<arr[mid])
	last=mid-1;
	//if it is greater, first will next of middle, and last will be last. This will continue and eventually we will find element
	else if(x>arr[mid])
	first=mid+1;
	//If we will find our wlwmwnt, it will be returned in first if. Otherwise element is not in the list and -1 will be returned.
	}
	return -1;
	}
	int main() {
	int n,arr[11],i,search,flag=0,first,last;
	//Enter number of elements in array
	printf("Enter the number of elements :\n");
	scanf("%d",&n);
	//Enter values in array
	printf("Enter the elements :\n");
	for(i=0;i<n;i++){
	scanf("%d",&arr[i]);
	}
	//Enter element to be searched
	printf("Enter the element to be searched :");
	scanf("%d",&search);
	first=0;
	last=n-1;
	//flag will have value of index of the found element or -1
	flag=BinarySearch(first,last,arr,search);
	if(flag>0)
	printf("The element %d is in position %d",search,flag);
	else
	printf("The element %d is not present in the array",search);
	return 0;
	}

view raw BinarySearch.c hosted with ❤ by GitHub