Binary Search in C++

Handling Multiple Matches in Binary Search

How do I handle cases where multiple elements match the search value in binary search?

Abstract art representing computer programming

When multiple elements in a container match the search value, binary search alone won't suffice to find all occurrences.

Instead, you should use std::ranges::lower_bound() and std::ranges::upper_bound() to identify the range of matching elements.

Using `lower_bound()` and `upper_bound()`

std::ranges::lower_bound() finds the first position where the element could be inserted, and std::ranges::upper_bound() finds the last position.

Example: Finding Range of Matching Elements

Here's an example demonstrating how to find the range of elements equal to a specific value:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<int> Nums{1, 2, 3, 4, 4, 4, 5};
7
8  int target = 4;
9  auto lower = std::ranges::lower_bound(
10    Nums, target);
11  auto upper = std::ranges::upper_bound(
12    Nums, target);
13
14  if (lower != Nums.end() && *lower == target) {
15    std::cout << "Range of " << target << ": [";
16    for (auto it = lower; it != upper; ++it) {
17      std::cout << *it
18        << (it + 1 != upper ? ", " : "");
19    }
20    std::cout << "]";
21  } else {
22    std::cout << "Element not found";
23  }
24}

1Range of 4: [4, 4, 4]

Benefits of This Approach

Efficiency: Using lower_bound() and upper_bound() together is efficient, with both operations being $O(log n)$ .
Exact Range: You get the exact range of matching elements, which is useful for further processing.

Example: Counting Matching Elements

You can count the number of occurrences of a value by finding the distance between lower_bound() and upper_bound():

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<int> Numbers{1, 2, 3, 4, 4, 4, 5};
7
8  int target = 4;
9  auto lower = std::ranges::lower_bound(
10    Numbers, target);
11  auto upper = std::ranges::upper_bound(
12    Numbers, target);
13
14  int count = std::distance(lower, upper);
15  std::cout << "Count of " << target << ": "
16    << count;
17}

1Count of 4: 3

Handling Non-Matching Cases

Always check if the lower_bound() result is within the container and matches the target value before using the range. This avoids incorrect results when the value is not present.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<int> Nums{1, 2, 3, 4, 4, 4, 5};
7
8  int target = 6;
9  auto lower = std::ranges::lower_bound(
10    Nums, target);
11  auto upper = std::ranges::upper_bound(
12    Nums, target);
13
14  if (lower != Nums.end() && *lower == target) {
15    int count = std::distance(lower, upper);
16    std::cout << "Count of " << target
17      << ": " << count;
18  } else {
19    std::cout << "Element not found";
20  }
21}

1Element not found

Summary

Using std::ranges::lower_bound() and std::ranges::upper_bound() allows you to efficiently handle multiple matches in a sorted container.

These functions provide the exact range of matching elements, making it easy to perform further operations like counting or iterating through the matches.

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.

5 months ago

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()