# Write a Binary Search Program in C++ With Example?

- In C++ the binary search algorithm will be only applied for only a sorted array. We cannot apply it on an unsorted array. So initially we have to sort the array element.

## Binary Search Algorithm C++

- Binary search algorithm in C++ relies on a divide and conquer strategy to find a value within an already-sorted collection.

- Binary search locates the position of an item in a sorted array.

- Binary search compare an input search key to the middle element of the array and the comparison determines whether the element equals the input, less than the input or greater.

- The return value is the element position in the array.

##### Working Flow OF Binary Search :

- Firstly the middle element of array is found and compared with value which user wanted to search in an array.

- If they are same then it will return the location of the required value.

- If they are not equal then it will break the array in half.

- If the middle element of array is smaller than the required number then it will search the first half of an array.

- If the middle element of array is greater than the required number then it will search the second half of an array.

- This process will continue until the required value is found or until the loop terminates or complete without founding the required value.

##### Binary Search Algorithm complexity :

- Worst case performance O(log n)
- Best case performance O(1)
- Average case performance O(log n)
- Worst case space complexity O(1)

## Example :

#include<iostream.h>
#include<conio.h>
void main()
{
int a[100],m,n,i,j,temp;
void binary(int a[100],int m,int n);
clrscr();
cout<<"Enter the size of array"; / get the size of the array
cin>>m;
cout<<"Enter array element"; / input value of the array
for(i=1;i<=m;i++)
{
cin>>a[i];
}
for(i=1;i<=m;i++)
{
for(j=i+1;j<=m;j++) / sorting the number
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
cout<<"Sorted array"; / Display the sorted array
for(i=1;i<=m;i++)
{
cout<<a[i];
}
cout<<"Enter the search element";
cin>>n;
binary(a,m,n); / call the function binary
getch();
}
void binary(int a[100],int m,int n) /binary search logic
{
int low=1,high=m,mid,flag=0;
while(low<=high&&flag==0)
{
mid=(low+high)/2;
if(n==a[mid])
{
flag=1;
cout<<"The number is found in "<<mid<<"position";
}
else if(n>a[mid])
{
low=mid+1;
}
else
{
high=mid-1;
}
}
if(flag==0)
{
cout<<"The number is not found";
}
}

## Output :

Enter the size of array: 5
Enter array element:
31
15
20
18
10
Sorted array:
10
15
18
20
31
Enter the search element: 18
The number is found in 3 position
Enter the search element: 9
The number is not found