Binary Search Algorithm with code in C++.

Binary Search is one the most popular and widely used search algorithms used to search whether a particular element is present in the given sorted array or not. It is much better than the Linear search algorithm because it is much faster.  

Problem: Given a sorted array of integers arr[ ] of size n and a target element x, write a C++ program to search the position of x in the given array.

Input: arr[ ] = {7, 10, 11, 15, 20, 30, 26}   x = 20

Output: 4
x is present at index 4.

Input: arr[ ] = {11, 15, 22, 30, 35, 43, 60, 75, 120}   x = 65

Output: -1
x is not present in the arr[ ].

Binary Search Explanation. 

When you try to find the target element in the given array, the worst-case scenario is that when you have to check each element of the given array and it leads to O(n) time complexity. But when the array elements are arranged in sorted order, you can use this extra information to reduce the time complexity to O(log n). 

• If you use a binary search on 100 elements to find your target, the worst-case scenario would be 10 searches. Can you imagine a huge performance improvement? 😲

You get this huge performance improvement because, for each iteration, you reduce the number of elements you will be looking at in half. The idea is to compare the target element to the middle element of the array. 

• If you find the target element is equal to the middle element, return the position of the middle element and stop.
• If the target element is smaller than the middle element, continue searching on the left side of the middle element. high = mid-1
• If the target element is greater than the middle element, continue searching on the right side of the middle element. low = mid+1
• Repeat all three steps until you find the matching element else return -1.

Example: C++ code for Binary Search Algorithm.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int key)
{ 

    int low = 0, high = n - 1; 

    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        //target is found
        if (arr[mid] == key)
        {
            return mid;
        }
        else if (arr[mid] < key) //target might be present in right half
        {
            low = mid + 1;
        }
        else    //target might be present in left half
        {
            high = mid - 1;
        }
    }
    return -1;
}

int main()
{

    int arr[] = {7, 10, 11, 15, 20, 30, 36};
    // size of given array
    int size = sizeof(arr) / sizeof(arr[0]);
    // target element to be find
    int x = 20;

    int index = binarySearch(arr, size, x);
    if (index == -1)
    {
        cout << "Value is not present in the given array." << endl;
    }
    else
    {
        cout << "Value present at index: " << index << endl;
    }
}

Value present at index: 4

int low = 0, high = n - 1;

int mid = (high + low) / 2; //formula 1 
int mid = low + (high - low) / 2; //formula 2