## Introduction to binary search :

*Binary Search* uses divide and search approach to search for an element in a sorted array. It divides the searching array into two parts and checks on which part the element lies. Based on that, it moves to either the *first* part or *second* part. Then it *divides* that part and follows the same rule.

Repeatedly, it narrows the interval down and finds the element if it exist.

## Time complexity :

The time complexity of *binary search* is *O(log n)*.

In this post, I will show you how to implement *binary search* in *C++*. I will show you both *recursive* and *iterative* way to solve it.

## Recursive method :

The below code implements binary search recursively :

```
using namespace std;
#include<iostream>
int findUsingBinarySearch(int arr[], int numToFind, int left, int right)
{
if (right >= left)
{
int midPosition = left + (right - left) / 2;
if (arr[midPosition] == numToFind)
return midPosition;
if (numToFind < arr[midPosition])
return findUsingBinarySearch(arr, numToFind, left, midPosition - 1s);
return findUsingBinarySearch(arr, numToFind, midPosition + 1, right);
}
return -1;
}
int main(void)
{
int givenArray[] = {1, 5, 7, 8, 10, 20, 28, 30, 40, 43, 50, 55, 60};
int numToFind;
cout<<"Enter a number to find :"<<endl;
cin>>numToFind;
int size = sizeof(givenArray) / sizeof(givenArray[0]);
int result = findUsingBinarySearch(givenArray, numToFind, 0, size - 1);
if (result != -1)
{
cout << "Element is found in the given array at index "<<result<<endl;
}
else
{
cout << "Element is not found in the given array"<<endl;
}
return 0;
}
```

- Here,
*findUsingBinarySearch*method is used to find one number in an array using binary search. ** - We are passing the array, number to find, left and right index of the search window.
- It returns
*-1*if it the number is not found. Else, it returns the index of the number.

## Iterative Approach :

```
using namespace std;
#include<iostream>
int findUsingBinarySearch(int arr[], int numToFind, int left, int right)
{
while (left <= right) {
int midPosition = left + (right - left) / 2;
if (arr[midPosition] == numToFind)
return midPosition;
if (arr[midPosition] < numToFind)
left = midPosition + 1;
else
right = midPosition - 1;
}
return -1;
}
int main(void)
{
int givenArray[] = {1, 5, 7, 8, 10, 20, 28, 30, 40, 43, 50, 55, 60};
int numToFind;
cout<<"Enter a number to find :"<<endl;
cin>>numToFind;
int size = sizeof(givenArray) / sizeof(givenArray[0]);
int result = findUsingBinarySearch(givenArray, numToFind, 0, size - 1);
if (result != -1)
{
cout << "Element is found in the given array at index "<<result<<endl;
}
else
{
cout << "Element is not found in the given array"<<endl;
}
return 0;
}
```

This is similar to the above approach. The only difference is that we are not calling one method recursively, but we are using one *while loop* that runs until *left* is *less than or equal* to *right*.

Similar to the above approach, it returns the *position* of the number if it is found. Else, it returns *-1*.

### Sample Output :

```
Enter a number to find :
31
Element is not found in the given array
Enter a number to find :
30
Element is found in the given array at index 7
```