Implement Binary Search using C++

If you’re in a computer science background, widening your technical horizons is the best thing you should do. However, your programming skills matter the most and one must continuously keep sharpening these skills. And to become a better programmer in the future. Though there are multiple things to focus on, one specific area you must focus on is the world of data structures. Data structures in general are particular approaches to solve problems so that computer resources get used minimum. In general, there are multiple data structures you can learn and implement as well. However, to keep things simple were going to start with some mediocre programs you must learn before moving on to complex algorithms. Therefore today we’re going to learn how to Implement Binary Search using C++.

 

What is Binary Search?

 

• Binary Search works only on the sorted arrays and is one of the most basic searching algorithms.

 

• The Array is firstly partitioned into two sections if the element we are searching for is less than the value at the middle index of an array. Then, we continue to partition and search for the element towards the left side. However, if the element is greater, we’ll continue to partition and search for the element towards the right side.

 

Also Read: Implement Radix Sort Using C++

 

What’s The Approach?

 

• We are going to start from the middle index of the array, if the middle index has the element we’re searching for we will simply return it.

 

• If the element is smaller than the element present at the middle index. Then, we’ll recursively search for it in the left subarray.

 

• If the element is greater than the element present at the middle index. Then, we’ll recursively search for it in the right subarray.

 

C++ Program To Implement Binary Search

Input:

2, 3, 4, 10, 40

 

Output:

Element is present at index 3

 

// C++ program to implement Binary Search
#include <bits/stdc++.h>
using namespace std;


int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;

        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;

        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);

        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }

    // We reach here when element is not
    // present in array
    return -1;
}

int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? cout << "Element is not present in array"
                : cout << "Element is present at index " << result;
    return 0;
}