Advanced C++ Programming and Algorithms

Implementing Binary Search in C++

Board Infinity
Board Infinity
Implementing Binary Search in C++

    OOPs (Object Oriented Programming) in C++

    A Quick Guide to Encapsulation in C++

    OOPs Abstraction in C++

    OOPS Polymorphism with C++

    Multiple Inheritance in C++

    Virtual Base Class in C++

    How to Perform Insertion Sort in C++?

    Counting Sort Algorithm: Using C++

    Bucket Sort Algorithm with C++

    Implementing Binary Search in C++

    Print all Permutations of given String: using C++

    Sliding Window Problem – C++ Implementation

    Implement Tower of Hanoi using C++

    Rabin Karp Algorithm: C++ Implementation

    Job Sequencing Problem with C++

    Biconnected Graph Algorithm with C++

    Hamiltonian Path Algorithm with 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.
  2. Start with an interval that encompasses the entire 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.