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

Question

Ryan McCombe · Accepted Answer

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.

Binary Search in C++

Handling Multiple Matches in Binary Search

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

Example: Finding Range of Matching Elements

Benefits of This Approach

Example: Counting Matching Elements

Handling Non-Matching Cases

Summary

Binary Search in C++

Professional C++

Questions & Answers

Handling Multiple Matches in Binary Search

Using lower_bound() and upper_bound()

Example: Finding Range of Matching Elements

Benefits of This Approach

Example: Counting Matching Elements

Handling Non-Matching Cases

Summary

Binary Search in C++

Questions & Answers

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