Binary Search in C++

Handling Binary Search in Unsorted Containers

How do I handle binary search if my container is not sorted?

Abstract art representing computer programming

Binary search only works efficiently on sorted containers. If your container is unsorted, you first need to sort it before performing a binary search.

Attempting a binary search on an unsorted container will lead to incorrect results because binary search relies on the order of elements to function correctly.

Here's a step-by-step approach to handle this:

Step 1: Sort the Container

First, use std::sort() to sort your container. For example, if you have a std::vector:

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

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

  std::sort(Numbers.begin(), Numbers.end());

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

Step 2: Perform Binary Search

After sorting, you can perform a binary search using std::binary_search() or std::ranges::binary_search():

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

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

  bool found = std::binary_search(
    Numbers.begin(), Numbers.end(), 4);

  std::cout << "The number 4 "
    << (found ? "was" : "was not") << " found";
}
The number 4 was found

Alternative: Sorting and Searching Together

If you often need to search unsorted containers, consider using data structures like std::set or std::map, which maintain order internally. These containers are always sorted, making searches efficient without the need for explicit sorting.

Using std::set:

#include <iostream>
#include <set>

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

  auto it = Numbers.find(4);

  if (it != Numbers.end()) {
    std::cout << "The number 4 was found";
  } else {
    std::cout << "The number 4 was not found";
  }
}
The number 4 was found

Sorting your container before performing binary search ensures you get correct results and leverages the efficiency of binary search.

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