C++ Program For Binary Search

 What is Binary Search?

There are two approach, simple approach is to do linear search. And approach is binary search.

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Recursive Implementation of Binary Search

#include <bits/stdc++.h>
using namespace std;

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

        if (arr[mid] == target)
            return mid;

        else if (arr[mid] > target)
            return binarySearch(arr, l, mid - 1, target);
  	
	else
        return binarySearch(arr, mid + 1, r, target);
    }
    return -1;
}
  
int main()
{
    int arr[] = { 12, 14, 19, 26, 29, 35, 40, 53 };
    int target = 35;
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = binarySearch(arr, 0, n - 1, target);

    (result == -1) ? cout << "Element not found"
                   : cout << "Element found at index " << result;
    return 0;
}

Output:

Element found at index 5

Iterative Implementation of Binary Search

#include <iostream>
using namespace std;

int binarySearch(int arr[], int l, int r, int target)
{
    while (l <= r)
    {
        int m = l + (r - l) / 2;
  
        if (arr[m] == target)
            return m;
  
        else if (arr[m] < target)
            l = m + 1;
  
        else
            r = m - 1;
    }
    return -1;
}
  
int main()
{
    int arr[] = { 12, 14, 19, 26, 29, 35, 40, 53 };
    int target = 35;
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = binarySearch(arr, 0, n - 1, target);
    
    (result == -1) ? cout << "Element not found"
                   : cout << "Element found at index " << result;
    return 0;
}

Output:

Element found at 5