Binary Search

Binary search is a more efficient search algorithm than linear search, but it requires the array to be sorted beforehand. It works by repeatedly dividing the search interval in half.

#include<stdio.h>
int binarySearch(int[], int, int);
int main(){
    int n, arr[50], key, pos;
    printf("Enter the number of elements: ");
	scanf("%d",&n);
	printf("Enter %d elements in sorted order: ",n);
	for(int i=0;i<n;i++){
		scanf("%d",&arr[i]);
	}
	printf("Enter the element to be searched: ");
	scanf("%d",&key);
	pos = binarySearch(arr, n, key);
    if(pos == -1){
        printf("Element not found in the array");
    }else{
        printf("In given array, element %d is at %d position",key, pos);
    }	
	return 0;
}

int binarySearch(int arr[],int n,int key){
    int low=0, high=n-1, mid;
    while(low<=high){
        mid = (low+high)/2;
        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]<key){
            low = mid+1;
        }
        else{
            high = mid-1;
        }
    }
    return -1;
}

Sample Input1 and Output1:

Enter the number of elements: 5
Enter 5 elements: 1 4 6 8 9
Enter the element to be searched: 6
In given array, element 6 is at 2 position

Sample Input2 and Output2:

Enter the number of elements: 5
Enter 5 elements: 1 4 6 8 9
Enter the element to be searched: 7
Element not found in the array