Re: Рекурсивний пошук по двовимірній впорядкованій матриці
Ось ця, наче, все знаходить:
bool
//std::pair<int, int>
find_in_matrix_lg_lg(
const std::vector<std::vector<int>>& matrix,
const int target
)
{
using Vec=std::vector<int>;
Vec vtarget={target};
auto vec_it=
std::lower_bound(matrix.begin(), matrix.end(), vtarget,
[](const Vec &a, const Vec &b){
return a.back()<b.back();
}
);
auto vec_it_last=std::upper_bound(matrix.begin(), matrix.end(), vtarget,
[](const Vec &a, const Vec &b){
return a.front()<b.front();
}
);
for(;vec_it!=vec_it_last; ++vec_it)
{
if(*vec_it->begin()>target || *(vec_it->end()-1)<target)continue;
auto it=std::lower_bound(vec_it->begin(), vec_it->end(), target);
if(*it==target)
{
return true;
//return {vec_it-matrix.begin(), vec_it->begin()-it};
}
}
return false;
// return{-1,-1};
}