Binary search with a vector

Question

I have a sorted vector V and I want to binary search the smallest index i for which V[i] <= target. This is my current attempt but it isn't working right.

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;
}

why rewrite binary_search algorithm? can't just use lower_bound,upper_bound ? — billz, Aug 03 '13 at 05:29
This seems exactly like your [previous now deleted question](http://stackoverflow.com/questions/18029382/binary-search-against-a-vector-of-pairs) ? Did you need to make a new one? — Borgleader, Aug 03 '13 at 05:31
possible duplicate of [Where can I get a "useful" C++ binary search algorithm?](http://stackoverflow.com/questions/446296/where-can-i-get-a-useful-c-binary-search-algorithm) — Borgleader, Aug 03 '13 at 05:34
@A.H. My question is a little different so Google doesn't quite help — MyNameIsKhan, Aug 03 '13 at 05:36
@AgainstASicilian wikipedia has a sample that works with vectors — A. H., Aug 03 '13 at 05:37
@Borgleader I had tried lower_bound(P.begin(), P.end(), target, [](pair lhs, int rhs) { return lhs.first < rhs; }); and that didn't work. Error error: cannot convert '__gnu_cxx::__normal_iterator*, std::vector > >' to 'int' in assignment — MyNameIsKhan, Aug 03 '13 at 05:44
@AgainstASicilian you need for a vector of pairs ? What is `V[mid]` ? — P0W, Aug 03 '13 at 05:46
@P0W I used vector in question because easier to word but since learning that lower_bound exists I want to use it for pair version — MyNameIsKhan, Aug 03 '13 at 05:47
@AgainstASicilian I don't know what you're doing but I've successfully searched an element in a vector of pairs using the answer from that question. — Borgleader, Aug 03 '13 at 05:57
@Borgleader Are you setting it into a variable? When I do it it throws error. How are you using it precisely. I am trying to get the index — MyNameIsKhan, Aug 03 '13 at 05:58
@AgainstASicilian What exactly do you mean by "setting it to a variable" — Borgleader, Aug 03 '13 at 05:59
@Borgleader I want to find int smallest_index = binary_search, that version does not seem to do that — MyNameIsKhan, Aug 03 '13 at 06:00
@AgainstASicilian Once you have the iterator to the element getting the index is trivial. — Borgleader, Aug 03 '13 at 06:01
I think maybe I have miscommunicated. I want the index that corresponds to the pair where the first element is the smallest possible that is <= target — MyNameIsKhan, Aug 03 '13 at 06:02
also it is not trivial, see http://stackoverflow.com/questions/2711653/c-how-to-convert-a-pointer-in-an-array-to-an-index but this doesn't work here by just subtracting P, so it is harder — MyNameIsKhan, Aug 03 '13 at 06:05

P0W · Accepted Answer · 2013-08-03T06:18:26.510

   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 !

Or why can't you use lower_bound for < target search :-

#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;
}

Neither of these work, last one doesn't know what Val is either, first half returns wrong value — MyNameIsKhan, Aug 03 '13 at 05:38
Is this something you assign? technically my vector is a vector of pairs and I am comparing first-elements, is it mid = lower_bound(P.begin(), P.end(), target, [](pair lhs, pair rhs) { return lhs.first < rhs.first; }); ? — MyNameIsKhan, Aug 03 '13 at 05:46

Binary search with a vector

1 Answers1