Binary search in C++
Find a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.
- File
binary_search.hpp, 29 lines- Level
- Native tests
- pass in this build
- Toolchain
- C++23, GCC 15 or Clang 21, with ASan and UBSan
- Test framework
- assert
- Run the tests
c++ -std=c++23 -Wall -Wextra -Wpedantic -Werror -fsanitize=address,undefined test_<name>.cpp && ./a.out
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
#pragma once
#include <cstddef>
#include <optional>
#include <span>
namespace algo {
// binary_search returns an index i with a[i] == x, or nothing when x is not in a. The span must be sorted.
template <typename T>
std::optional<std::size_t> binary_search(std::span<const T> a, const T& x) {
std::size_t lo = 0, hi = a.size(); // @line L1
while (lo < hi) { // @line L2
std::size_t mid = lo + (hi - lo) / 2; // @line L3
if (a[mid] < x) { // @line L4
lo = mid + 1; // @line L5
} else if (x < a[mid]) { // @line L6
hi = mid; // @line L7
} else {
return mid; // @line L8
}
}
return std::nullopt; // @line L9
}
} // namespace algo
test_binary_search.cpp 41 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <string>
#include <vector>
#include "binary_search.hpp"
int main() {
const std::vector<int> a{2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
std::span<const int> s(a);
assert(algo::binary_search(s, 23) == 5);
assert(algo::binary_search(s, 2) == 0);
assert(algo::binary_search(s, 91) == 9);
assert(!algo::binary_search(s, 30));
assert(!algo::binary_search(s, 1));
assert(!algo::binary_search(s, 100));
assert(!algo::binary_search(std::span<const int>{}, 1));
const std::vector<std::string> w{"ant", "bee", "cat"};
assert(algo::binary_search(std::span<const std::string>(w), std::string("bee")) == 1);
std::mt19937 rng(2150);
for (int t = 0; t < 2000; t++) {
std::vector<int> b(rng() % 31);
for (auto& v : b) v = static_cast<int>(rng() % 41) - 20;
std::ranges::sort(b);
int x = static_cast<int>(rng() % 51) - 25;
auto got = algo::binary_search(std::span<const int>(b), x);
if (std::ranges::find(b, x) != b.end()) {
assert(got && b[*got] == x);
} else {
assert(!got);
}
}
std::cout << "ok\n";
}
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work