Handling Binary Search in Unsorted Containers

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:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<int> Numbers{3, 1, 4, 5, 2};
7
8  std::sort(Numbers.begin(), Numbers.end());
9
10  for (const auto& num : Numbers) {
11    std::cout << num << " ";
12  }
13}

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

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector<int> Numbers{1, 2, 3, 4, 5};
7
8  bool found = std::binary_search(
9    Numbers.begin(), Numbers.end(), 4);
10
11  std::cout << "The number 4 "
12    << (found ? "was" : "was not") << " found";
13}

1The 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:

1#include <iostream>
2#include <set>
3
4int main() {
5  std::set<int> Numbers{3, 1, 4, 5, 2};
6
7  auto it = Numbers.find(4);
8
9  if (it != Numbers.end()) {
10    std::cout << "The number 4 was found";
11  } else {
12    std::cout << "The number 4 was not found";
13  }
14}

1The number 4 was found

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