C++ Programs Binary Search

Binary Search is a search algorithm that is used to find whether a given element is present in the sorted array or not.

Syntax

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

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

        if (arr[mid] < x)
            l = mid + 1;
        else
            r = mid - 1;
    }

 return -1;
}

Example

#include <iostream>
using namespace std;

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

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

        if (arr[mid] < x)
            l = mid + 1;
        else
            r = mid - 1;
    }

    return -1;
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 4;

    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1)
        cout << "Element not found.";
 else
        cout << "Element found at index " << result;

    return 0;
}

Output

Element found at index 3

Explanation

In the above example, we are searching for the element "4" in the sorted array "arr". We start by setting the left and right indices as "0" and "n-1" respectively. We then find the middle element and compare it with the search element. If it matches, we return the index. If it is less than the search element, we discard the left half of the array and set the left index as "mid+1". If it is greater than the search element, we discard the right half of the array and set the right index as "mid-1". We repeat this process until the element is found or the left index becomes greater than the right index.

Use

Binary Search is used to find a given element in a sorted array. It is an efficient algorithm and has a time complexity of O(log n).

Important Points

• Binary Search works only on sorted arrays.
• The time complexity of Binary Search is O(log n).
• The array needs to be sorted in ascending or descending order before applying Binary Search.

Summary

In summary, Binary Search is an efficient algorithm used to search for a given element in a sorted array. It has a time complexity of O(log n). Binary search works by dividing the array into halves and discarding the half in which the element is not expected to be present.