Writing your first microbenchmark

We'll try to benchmark how much faster a lookup takes when it's done using bisection in a sorted vector as compared to just going through it linearly. Let's start with code that will create the sorted vector:

using namespace std::ranges;

template <typename T>
auto make_sorted_vector(std::size_t size) {
  auto sorted = std::vector<T>{};
  sorted.reserve(size);

  auto sorted_view = views::iota(T{0}) | views::take(size);
  std::ranges::copy(sorted_view, std::back_inserter(sorted));
  return sorted;
}

Our vector will contain size elements with all the numbers from 0 to size - 1 in ascending order. Let's now specify the element we're looking for and the container size:

constexpr auto MAX_HAYSTACK_SIZE = std::size_t{10'000'000};
constexpr auto NEEDLE = 2137;

As you can see, we'll benchmark how long it takes to find a needle in a haystack. The simple linear search can be implemented as follows:

void linear_search_in_sorted_vector...