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?

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.

### Usinglower_bound()andupper_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:

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

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

int target = 4;
auto lower = std::ranges::lower_bound(
Nums, target);
auto upper = std::ranges::upper_bound(
Nums, target);

if (lower != Nums.end() && *lower == target) {
std::cout << "Range of " << target << ": [";
for (auto it = lower; it != upper; ++it) {
std::cout << *it
<< (it + 1 != upper ? ", " : "");
}
std::cout << "]";
} else {
}
}
Range 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():

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

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

int target = 4;
auto lower = std::ranges::lower_bound(
Numbers, target);
auto upper = std::ranges::upper_bound(
Numbers, target);

int count = std::distance(lower, upper);
std::cout << "Count of " << target << ": "
<< count;
}
Count 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.

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

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

int target = 6;
auto lower = std::ranges::lower_bound(
Nums, target);
auto upper = std::ranges::upper_bound(
Nums, target);

if (lower != Nums.end() && *lower == target) {
int count = std::distance(lower, upper);
std::cout << "Count of " << target
<< ": " << count;
} else {
}
}
Element 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.

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

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.