C++ algorithm: std::binary_search Function Template

C++ std::binary_search

The std::binary_search function in C++ checks if a given element exists in a sorted range using the binary search algorithm. The range must be sorted in ascending order or according to a custom comparison function.

This function is efficient, with a time complexity of O(log n), making it suitable for quick lookups in large datasets.

---

Syntax of std::binary_search

template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);

template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Parameters of std::binary_search

Parameter	Description
first, last	Forward iterators defining the range to search. The range is [first, last).
value	The value to search for in the range.
comp (optional)	A binary comparison function that defines the order of elements. Defaults to <.

---

Return Value of std::binary_search

Returns true if the specified value exists in the range [first, last). Returns false otherwise.

---

Examples for std::binary_search

Example 1: Basic Usage of std::binary_search

This example demonstrates searching for a value in a sorted vector:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> nums = {10, 20, 30, 40, 50};

    int value = 30;

    if (std::binary_search(nums.begin(), nums.end(), value)) {
        std::cout << value << " is found in the range." << std::endl;
    } else {
        std::cout << value << " is not found in the range." << std::endl;
    }

    return 0;
}

Explanation:

1. Include necessary headers:
   • <iostream>: Used for input/output operations.
   • <algorithm>: Includes the std::binary_search function for searching within a sorted range.
   • <vector>: Used for the std::vector container.
2. Initialize a sorted vector:
   • A vector named nums is initialized with the elements {10, 20, 30, 40, 50}.
   • The vector is sorted in ascending order, which is a prerequisite for using std::binary_search.
3. Define a value to search:
   • An integer variable value is initialized with 30, which is the target to search for within the vector.
4. Perform the binary search:
   • The function std::binary_search is called with three arguments:
     • nums.begin(): Iterator pointing to the beginning of the range.
     • nums.end(): Iterator pointing to the end of the range.
     • value: The target value to search for.
   • If value is found within the range, the function returns true; otherwise, it returns false.
5. Check and output the result:
   • If std::binary_search returns true, the program outputs: "30 is found in the range.".
   • If it returns false, the program outputs: "30 is not found in the range.".
   • For the given input, the output is: "30 is found in the range.".

Output:

30 is found in the range.

Example 2: Using a Custom Comparison Function for std::binary_search

This example demonstrates searching for a value in a descendingly sorted vector using a custom comparison function:

#include <iostream>
#include <algorithm>
#include <vector>

bool descending(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> nums = {50, 40, 30, 20, 10};

    int value = 30;

    if (std::binary_search(nums.begin(), nums.end(), value, descending)) {
        std::cout << value << " is found in the range." << std::endl;
    } else {
        std::cout << value << " is not found in the range." << std::endl;
    }

    return 0;
}

Output:

30 is found in the range.

---

Exception Handling in std::binary_search

The std::binary_search function does not throw exceptions on its own. However, the comparison function passed as an argument may throw exceptions, which can be caught and handled appropriately.

Example 1: Exception in Custom Comparison Function

This example demonstrates handling exceptions in a custom comparison function:

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdexcept>

bool faulty_compare(int a, int b) {
    if (a == 30 || b == 30) {
        throw std::runtime_error("Comparison involving 30 is not allowed.");
    }
    return a < b;
}

int main() {
    std::vector<int> nums = {10, 20, 30, 40, 50};

    try {
        if (std::binary_search(nums.begin(), nums.end(), 30, faulty_compare)) {
            std::cout << "30 is found in the range." << std::endl;
        } else {
            std::cout << "30 is not found in the range." << std::endl;
        }
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught: Comparison involving 30 is not allowed.