C++ Program to Perform Binary Search on a Sorted List

1. Introduction

Binary search is an efficient algorithm for finding a specific value within a sorted list. It halves the portion of the list that needs to be searched each time by comparing the middle element to the target value. If the middle element is the target value, the search ends. Otherwise, if the target value is less or greater than the middle element, the search continues in the lower or upper half of the list respectively. 

In this blog post, we'll explore a C++ program to perform a binary search on a sorted list.

2. Program Overview

1. Define and initialize the sorted array or list.

2. Input the number to be searched.

3. Determine the middle of the list.

4. Compare the middle element with the searched number.

5. Depending on the comparison, either end the search, check the lower half, or check the upper half.

6. Continue until the number is found or the sublist has one element.

3. Code Program

#include <iostream>
using namespace std;

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

        // Check if x is present at mid
        if (arr[mid] == x)
            return mid;

        // If x is greater, ignore left half
        if (arr[mid] < x)
            l = mid + 1;

        // If x is smaller, ignore right half
        else
            r = mid - 1;
    }

    // If we reach here, then the element was not present
    return -1;
}

int main() {
    int n;
    cout << "Enter the number of elements in the array: ";
    cin >> n;
    int arr[n];

    // Reading array elements from the user
    cout << "Enter " << n << " sorted numbers: ";
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int x;
    cout << "Enter the number to be searched: ";
    cin >> x;

    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? cout << "Number not present in array"
                   : cout << "Number " << x << " is at index " << result;

    return 0;
}

Output:

Enter the number of elements in the array: 5
Enter 5 sorted numbers: 2 3 6 8 9
Enter the number to be searched: 9
Number 9 is at index 4

4. Step By Step Explanation

1. Binary Search Function: This function recursively divides the list into half until the searched number is found or the sublist has just one element.

2. Middle Element: It's calculated by adding the lower bound (l) to half the difference of the upper bound (r) and l.

3. Comparison: If the middle element is the number we are searching for, the search ends. If the middle element is less than the number, we check the right half of the list and if it's more, we check the left half.

4. Result: After executing the binary search, we check the result to see if the number was found or not.

Binary search is much more efficient than linear search for large datasets, but it requires the list to be sorted in advance.