Binary Search using C

Binary Search

Binary search is a searching technique in a given sorted(ascending or descending) collection of the elements. We all know that there are two types of searching Linear Search, Binary Search, where Linear Search time complexity depends on the no of the element present in the collections I's Time complexity is O(n), whereas Binary Search depends on the height of the tree that is why Time complexity is O(log n). Binary search can be implemented by divide and conquer approach

Divide and Conquer: =It is an approach to solve the bigger problem. If a problem P(big) is given of size=n, which can not be solved at a time then it can be broken into Pk subproblem and obtain a solution for each of them then after combining  all those solutions we can get solutions of the main problem

Binary Search using Iteration
//binary search using iteration
#include<stdio.h>
#include<conio.h>
int ar[20];
int bsearch(int ,int);//prototype declaration
void main()
{
int flag,n,i,key;
clrscr();
printf("Enter no of element :=");
scanf("%d",&n);
//taking input from user
//input must be in sorted order
printf("\nEnter elements in sorted order\n");
for(i=0;i<n;i++)
{
printf("\nEnter Ar[%d]:=",i);
scanf("%d",&ar[i]);
}
printf("\nEnter the key u want to search:=");
scanf("%d",&key);
flag=bsearch(n,key);
if(flag==0)
{
printf("\nKey not found!!");
}
else
{
printf("\nKey %d found at [%d] position",key,flag+1);
}
getch();
}

//function defination start

int bsearch(int n,int key)
{
int mid,low=0,high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(ar[mid]==key)
{
return mid;//if element found at mid position return mid
}
else if(key<ar[mid])
{
high=mid-1;//if element is less then mid then upper is shifted to (mid-1)
}
else
{
low=mid+1;//if element is less then mid then upper is shifted to (mid-1)
}
}
return 0;

}

Source code : https://github.com/shouvik126/binary_search-iteration-

Output :

Binary Search using recursion : 

//Binary search using recursion

#include<stdio.h>

#include<conio.h>

int ar[30];

int bsearch(int ,int ,int);//prototype declaration

void main()

{

int low,high,n,i,key,flag;

clrscr();

printf("\nEnter no of element:=");

scanf("%d",&n);

printf("\nEnter elements in sorted order\n");

for(i=0;i<n;i++)

{

printf("\nEnter Ar[%d] :=",i);

scanf("%d",&ar[i]);

}

printf("\nEnter the key u want to search:=");

scanf("%d",&key);

low=0;

high=n-1;

flag=bsearch(low,high,key);//function called

if(flag==0)

{

printf("\nKey not found!!!");

}

else

{

printf("\nKey %d found at [%d] position@@",key,flag+1);

}

getch();

}

//function defination start

int bsearch(int low,int high,int key)

{

int mid;

if(low==high)

{

if(ar[low]==key)

{

return low;//one element exist with in range

}

else

return 0;

}

else

{

mid=(low+high)/2;

if(key==ar[mid])

return mid; //if element found at middle of the array

else if(key<ar[mid])

return bsearch(low,mid-1,key);//if searching key is less then ar[mid]

else

return bsearch(mid+1,high,key);//if searching key is greater then ar[mid]

}

}

Source Code : https://github.com/shouvik126/binary_search_recursion

Output :