Binary Search:
Binary Search involves reducing the search range to half by dividing the range into half of its original size. Binary Search operates upon sorted array. It compares the element at the mid of this range with the value to be searched, if the value is smaller than the mid value, then the value is looked up in the range from first element to mid, otherwise the new search range becomes mid to last element. This process continues until the required element is located or lower bound becomes greater than upper bound. Efficiency of Binary Search is O(log2n) in average and worst case and is O(1) in best case. The ‘C’ program to perform Binary Search is given below:
/* Binary Search */
#include <stdio.h>
#define MAX 10
int main(){
int arr[MAX],i,n,val;
int lb,ub,mid;
printf(“nEnter total numbers?”);
scanf(“%d”,&n);
for(i=0;i<n;i++){
printf(“nEnter number?”);
scanf(“%d”,&arr[i]);
}
printf(“nEnter the value to search?”);
scanf(“%d”,&val);
lb=0;ub=n-1;
while(lb<=ub){
mid=(lb+ub)/2;
if(val<arr[mid])
ub = mid-1;
else if(val>arr[mid])
lb = mid+1;
else {
printf(“nNumber found…!”);
return;
}
}
printf(“nNumber not found…!”);
}