Binary Search in C++

Understanding the Iterator Returned by lower_bound()

What is the significance of the iterator returned by std::ranges::lower_bound()?

Abstract art representing computer programming

The iterator returned by std::ranges::lower_bound() is significant because it points to the first element in the range that is not less than the specified value. This makes it useful for various operations in sorted containers.

Key Uses of lower_bound() Iterator

  1. Finding an Element: It helps locate where an element would be if it were present in the container.
  2. Insertion Point: It indicates where a new element should be inserted to maintain the sorted order.
  3. Range Queries: It can be used to find the starting point for range-based operations.

Example: Finding an Element

If the element is found, lower_bound() returns an iterator to the element. If not, it returns an iterator to the first element greater than the value or the end of the container.

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

int main() {
  std::vector<int> Numbers{1, 2, 3, 4, 5};

  auto it = std::ranges::lower_bound(Numbers, 3);

  if (it != Numbers.end() && *it == 3) {
    std::cout << "Element found: " << *it;
  } else {
    std::cout << "Element not found";
  }
}
Element found: 3

Example: Insertion Point

If you want to insert a new element while maintaining the sorted order, lower_bound() gives you the exact position:

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

int main() {
  std::vector<int> Numbers{1, 2, 3, 5};

  int newElement = 4;
  auto it = std::ranges::lower_bound(
    Numbers, newElement);

  Numbers.insert(it, newElement);

  for (const auto& num : Numbers) {
    std::cout << num << " ";
  }
}
1 2 3 4 5

Range Queries

lower_bound() is also useful for range queries when combined with upper_bound(). Together, they can find all elements equal to a certain value.

Understanding lower_bound() in Practice

  • Element Exists: If the element exists, lower_bound() points to it.
  • Element Does Not Exist: If the element does not exist, lower_bound() points to where it would be inserted.
  • End Iterator: If the returned iterator is the end, the element is greater than all elements in the container.

Handling Edge Cases

Always check if the returned iterator is the end of the container before dereferencing it to avoid errors.

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

int main() {
  std::vector<int> Numbers{1, 2, 3, 5};

  int searchValue = 6;
  auto it = std::ranges::lower_bound(
    Numbers, searchValue);

  if (it != Numbers.end()) {
    std::cout << "The number " << searchValue
      << " would be in position "
      << std::distance(Numbers.begin(), it);
  } else {
    std::cout << "The number " << searchValue
      << " is greater than all elements\n";
  }
}
The number 6 is greater than all elements

The iterator from std::ranges::lower_bound() provides a powerful way to manage sorted containers, facilitating efficient searches, insertions, and range-based operations.

This Question is from the Lesson:

Binary Search in C++

An introduction to the advantages of binary search, and how to use it with the C++ standard library algorithms binary_search(), lower_bound(), upper_bound(), and equal_range()

Answers to questions are automatically generated and may not have been reviewed.

This Question is from the Lesson:

Binary Search in C++

An introduction to the advantages of binary search, and how to use it with the C++ standard library algorithms binary_search(), lower_bound(), upper_bound(), and equal_range()

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved