Бинарный поиск с вектором
У меня есть отсортированный вектор V, и я хочу выполнить бинарный поиск наименьшего индекса i, для которого V [i] <= цель. Это моя текущая попытка, но она не работает правильно.
int hi= L;
int lo= 1;
int mid = (hi+lo)/2;
while (hi>lo+1){
if (V[mid]>=target) hi=mid;
else lo= mid;
mid=(hi+lo)/2;
}
Решение
auto s=v.begin();
auto e=v.end();
auto L = std::distance(s, e);
while (L > 0)
{
auto half = L/2;
auto mid = s;
std::advance(mid, half);
if (*mid < target)
{
s = mid;
++s;
L = L - half - 1;
}
else
L = half;
}
//s is your element !
Или почему вы не можете использовать lower_bound для < target поиск: —
#include<iostream>
#include<vector>
#include<algorithm>
typedef std::pair<int,int> mypair;
struct comp_pairs
{
bool operator()( const mypair lhs,
const int& rhs ) const
{ return lhs.first < rhs; }
bool operator()( const int& lhs,
const mypair& rhs ) const
{ return lhs<rhs.first; }
};
int main()
{
std::vector<mypair> V;
V.push_back(std::make_pair(2,9));
V.push_back(std::make_pair(3,8));
V.push_back(std::make_pair(4,7));
V.push_back(std::make_pair(5,6));
int target =4;
auto pos=std::lower_bound(V.begin(),V.end(),target,comp_pairs());
std::cout << "Position " << (pos- V.begin()) << std::endl;
}
Другие решения
Других решений пока нет …
detector