# Implementing Binary Search in C++

## Introduction

The interval search algorithm family includes the binary search algorithm. Comparing this approach to the linear search algorithm, it is significantly more effective. Only sorted data structures can be used for binary search. The search space is divided in half and the centre of the sorted data structure is continually targeted by this method until the match is discovered. Binary search algorithm's temporal complexity is O (Log n).

## Working

1. Divide the search interval in half periodically to search the sorted array.
3. Narrow the interval to the bottom half if the search key's value is smaller than the item in the interval's midpoint.
4. If not, then make it narrow to the top half.
5. Continue checking until the interval is empty or the value is located.
1. Take input array, left, right & x
2. START LOOP – when left exceeds or is equal to right
• mid = left + (right-left)/2
• if(arr[mid]==x) then
• return m
• else if(arr[mid] less than x) then
• left = m + 1
• else
• right= mid – 1
1. END LOOP
2. return -1
 #include < iostream >  using namespace std;int BSearch(int arr[], int left, int right, int x) {  while (left <= right) {    int mid = left + (right - left) / 2;    if (arr[mid] == x) {      return mid;    } else if (arr[mid] < x) {      left = mid + 1;    } else {      right = mid - 1;    }  }  return -1;}int main() {  int myarr[10];  int num;  int output;  cout << "Please enter 10 elements ASCENDING order" << endl;  for (int i = 0; i < 10; i++) {    cin >> myarr[i];  }  cout << "Please enter an element to search" << endl;  cin >> num;  output = BSearch(myarr, 0, 9, num);  if (output == -1) {    cout << "No Match Found" << endl;  } else {    cout << "Match found at position: " << output << endl;  }  return 0;}
write your code here: Coding Playground

## Algorithmic Complexity

 Best Case Time Complexity O(1) Worst Case Time Complexity O(log n) Average Time Complexity O(log n) Space Complexity O(1)

## Conclusion

I hope this tutorial helped you understand how binary search is implemented in C++. This method is frequently used to determine an element's location in an array or list that has been sorted. We spoke about the iterative and recursive approaches to binary search. With a few little changes to the code, both approaches use the same logic. If you want to study C++, you may read some of our other articles.