Is there a way to binary search a column of a 2D std::vector without creating a new vector?

Question

I am solving Leetcode 74: Search a 2D Matrix in C++20 in which a partially ordered (in row-major) 2D matrix is to be searched for an element.

The solution finds a row in which the target must reside, if at all, and searches in that row.

To do that, it binary-searches on the rows' last elements, looking for the first row with a last element greater equal to the target.

Is there a way to use std::lower_bound to search the rightmost column, without creating the rightmost column as a std::vector?

[Example]

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

auto searchMatrix(auto&& matrix, auto target) {
  // MAYBE use an iterator?
  auto rightmost_col = [&]{
    using Col = std::remove_reference<decltype(matrix[0])>::type;
    auto rightmost_col = Col();
    for (auto i : std::views::iota(0, std::ssize(matrix))) {
      rightmost_col.push_back(matrix[i].back());
    }
    return rightmost_col;
  }();

  auto find = [&](const auto& space) -> std::optional<decltype(target)> {
    auto pos = std::ranges::lower_bound(space, target);
    if (pos == std::ranges::end(space)) return std::nullopt;
    return pos - std::ranges::begin(space);
  };

  if (auto candidate_row = find(rightmost_col)) {
    if (auto candidate_col = find(matrix[*candidate_row])) {
      return matrix[*candidate_row][*candidate_col] == target;
    }
  }
  return false;
}

auto main([[maybe_unused]] int argc, [[maybe_unused]] char** argv) -> int {
  auto matrix = std::vector<std::vector<int>>{{1,3,5,7}, {10,11,16,20}, {23,30,34,60}};
  auto target = 3;
  auto result = searchMatrix(matrix, target);
  std::cout << std::boolalpha << result << std::endl;
}

I tried using a view, but certain concepts were not satisified.

Answer 1

You can use views::transform to create a view consisting of the last element of each vector:

auto searchMatrix(auto&& matrix, auto target) {
  auto rightmost_col = 
    matrix | std::views::transform([](const auto& inner) -> const auto& {
               return inner.back();
             });
  // ...
}

Demo

Or you can do a binary search directly on matrix | std::views::join (with only one line)

auto searchMatrix(auto&& matrix, auto target) {
  return std::ranges::binary_search(matrix | std::views::join, target);
}

Demo