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:

#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 {
    std::cout << "Element not found";
  }
}
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(logn)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 {
    std::cout << "Element not found";
  }
}
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()

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