C++ Binary Search Algorithm Stl

4 min read Jul 01, 2024

C++ Binary Search Algorithm: STL Implementation

The Binary Search algorithm is a highly efficient search algorithm used to find a specific element within a sorted array. It works by repeatedly dividing the search interval in half. This approach significantly reduces the time required for searching compared to linear search.

In C++, the Standard Template Library (STL) provides a powerful and convenient way to implement binary search using the binary_search() function.

Using `binary_search()` Function

The binary_search() function takes three arguments:

Iterator to the beginning of the array: This points to the first element of the sorted array.
Iterator to the end of the array: This points to one past the last element of the array.
Value to be searched: This is the element you want to find.

The function returns a boolean value: true if the element is found and false otherwise.

#include 
#include 
#include 

int main() {
  std::vector arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

  int search_value = 12;

  if (std::binary_search(arr.begin(), arr.end(), search_value)) {
    std::cout << search_value << " found in the array." << std::endl;
  } else {
    std::cout << search_value << " not found in the array." << std::endl;
  }

  return 0;
}

Output:

12 found in the array.

Finding the Element's Position

To find the exact position of the searched element within the array, we can use the lower_bound() function. This function returns an iterator pointing to the first element not less than the specified value.

#include 
#include 
#include 

int main() {
  std::vector arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

  int search_value = 12;

  auto it = std::lower_bound(arr.begin(), arr.end(), search_value);
  if (it != arr.end() && *it == search_value) {
    std::cout << search_value << " found at index: "
              << std::distance(arr.begin(), it) << std::endl;
  } else {
    std::cout << search_value << " not found in the array." << std::endl;
  }

  return 0;
}

Output:

12 found at index: 3

Benefits of STL `binary_search()` Function

Simplicity: The binary_search() function provides a convenient and concise way to implement binary search without writing complex code.
Efficiency: The STL implementation of binary search is highly optimized for performance.
Flexibility: The binary_search() function can be used with various data structures like arrays, vectors, and lists.

Conclusion

The STL binary_search() function offers an efficient and user-friendly way to implement binary search in C++. Its simplicity and flexibility make it a valuable tool for searching through sorted data structures. Remember that the array must be sorted for the binary_search() function to work correctly.

C++ Binary Search Algorithm Stl