CODEWITHSUNDEEP
c++sortingc++11searchbinary-search
Nick
Nick

Reputation: 10499

Seek item within vector

I have a vector of real values, sorted by increasing order.

These values can be within the range [0, 1]. Then I pick a value x within this range and I need to find which is the index of the smaller value greater or equal to x.

I can solve this problem by iterating over the whole array:

vector<double> values;
double x;

for (auto val : values)
{
    if (x <= values)
    {
        // found
        break;
    }
}

Is there a faster way to get the same result? I was thinking about a binary search, but how to implement it?

Upvotes: 2

Views: 762

Answers (4)

gsamaras
gsamaras

Reputation: 73366

You know SO is not a site that you request someone to write you the code, so take this example of std::binary_search and make your way:

// binary_search example
#include <iostream>     // std::cout
#include <algorithm>    // std::binary_search, std::sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {1,2,3,4,5,4,3,2,1};
  std::vector<int> v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1

  // using default comparison:
  std::sort (v.begin(), v.end());

  std::cout << "looking for a 3... ";
  if (std::binary_search (v.begin(), v.end(), 3))
    std::cout << "found!\n"; else std::cout << "not found.\n";

  // using myfunction as comp:
  std::sort (v.begin(), v.end(), myfunction);

  std::cout << "looking for a 6... ";
  if (std::binary_search (v.begin(), v.end(), 6, myfunction))
    std::cout << "found!\n"; else std::cout << "not found.\n";

  return 0;
}

As Piotr said, this will not give you the index, but a yes/no answer. However, is should be the simplest approach, thus the fastest.

Upvotes: 0

0xLLLLH
0xLLLLH

Reputation: 34

The function lower_bound might meet your demand,and you can use it like below:

iter =lower_bound(values.begin(),values.end(),x);

Upvotes: 1

Piotr Skotnicki
Piotr Skotnicki

Reputation: 48447

Use std::lower_bound:

#include <iterator>
#include <algorithm>

std::distance(begin(values)
            , std::lower_bound(begin(values), end(values), x));

If the item doesn't exist, it'll give you an index one greater than that of the last element.

DEMO

Upvotes: 2

Chuanzhen Wu
Chuanzhen Wu

Reputation: 47

You can use operator[] to directly access the items in a vector just like an array, instead of using an iterator to start from the begin. I assume you already know Binary Search. Implement it in an array is something you can find anywhere, so I won't explain it to you here. Just treat the vector as an array.

Upvotes: 0

Related Questions