Find position of element using binary_search

[Angus]

Hello

int records[] = {1,2,3,4,5,6,7,8,9};
int len = sizeof(records)/sizeof(int);
bool fnd = std::binary_search(records, records+len, 7);

This is fine to find if element exists in array. But how do I find
the position in the array?

Angus

 

[Michael Doubez]

   int records[] = {1,2,3,4,5,6,7,8,9};
   int len = sizeof(records)/sizeof(int);
   bool fnd = std::binary_search(records, records+len, 7);

This is fine to find if element exists in array.  But how do I find
the position in the array?

int * it = std::lower_bound( begin(records), end(records) , 7);

bool fnd = it != end(records) && *it == 7;

int index = std::distance( begin(records), it);

Note that if the table is short or if a binary search is not critical,
std::find() is acceptable (and in some cases, prefered).

 

[Juha Nieminen]

Note that if the table is short or if a binary search is not critical,
std::find() is acceptable (and in some cases, prefered).

Why is it preferred? How short is "short"? Have you measured it?
(I haven't, but my guess is that std::find() might be faster than
std::lower_bound() if there are about 10 elements or less, and even
then the speed difference is probably minimal.)

 

[Jonathan Lee]

  Why is it preferred? How short is "short"? Have you measured it?
(I haven't, but my guess is that std::find() might be faster than
std::lower_bound() if there are about 10 elements or less, and even
then the speed difference is probably minimal.)

Not measuring here, but I would agree that about 10 is right. The
number of elements you need to check is about the same in both cases.
A binary search, though, is going to have more instructions per
iterations, and the CPU will have a harder time predicting where
the next data read will be from. Of course, on modern CPUs I doubt
that's much of an issue. So for the sake of simplicity I always use
lower_bound.

--Jonathan

 

[James Kanze]

Why is it preferred?

Because it's easier to manage. You don't have to keep the table
sorted. And the iterator returned by find tells you immediately
whether you've found what you were looking for or not.

How short is "short"?

That depends on the application, and the frequency of the
search. In general, the rule is: use std::find until you have a
performance problem. Then evaluate your alternatives. No point
in adding complexity unless you have to.

 

[James Kanze]

...]
So for the sake of simplicity I always use
lower_bound.

For the sake of simplicity, you always use the more complicated
solution? That doesn't sound right.

 

[Jorgen Grahn]

...]
So for the sake of simplicity I always use
lower_bound.

For the sake of simplicity, you always use the more complicated
solution? That doesn't sound right.

It sounds right to me (except maybe the "always", but the context of
that one is lost). If the problem is naturally suited to binary
search, if the number of elements today seems small, but I cannot
easily predict that it will always stay that way -- I might keep the
vector sorted and do binary searches.

/Jorgen

 

[Juha Nieminen]

...]
So for the sake of simplicity I always use
lower_bound.

For the sake of simplicity, you always use the more complicated
solution? That doesn't sound right.

I think that the idea was that it's simpler to use std::lower_bound
than writing a conditional where you use std::find in one branch and
std::lower_bound in the other (the condition being the amount of
elements).

 

[Juha Nieminen]

That depends on the application, and the frequency of the
search. In general, the rule is: use std::find until you have a
performance problem. Then evaluate your alternatives. No point
in adding complexity unless you have to.

I have never fully agreed with the "KISS until you have a performance
problem, only then go back and refactor" principle. If you know that the
program should be prepared for larger amounts of data (or other similar
parameters that will make it need more calculations), then do it right the
first time. It's better to do a bit more work now than having to go back
later and having to refactor existing code. This especially so when we are
talking about a very minimal amount of work (such as choosing between
std::find and std::lower_bound).

 

[James Kanze]

I have never fully agreed with the "KISS until you have a performance
problem, only then go back and refactor" principle.

It is, never the less, the solution which results in the best
performance, when performance is a problem.

If you know that the program should be prepared for larger amounts of
data (or other similar parameters that will make it need more
calculations), then do it right the first time.

If you know up front that using an O(n) algorithm will cause a
performance problem, then you respond to that performance problem up
front. This is more often an issue when the algorithm is O(n^2),
however.

It's better to do a bit more work now than having to go back
later and having to refactor existing code.

If you've written the code cleanly, the changes will be isolated. If
you have to "refactor" anything, then you were probably paying too
much
attention to performance up front, and not enough to encapsulation.

 

[Jonathan Lee]

On Mar 9, 4:54 am, Juha Nieminen <[email protected]> wrote:

    ...]

So for the sake of simplicity I always use
lower_bound.

For the sake of simplicity, you always use the more complicated
solution?  That doesn't sound right.

It's simpler to do one over both (i.e., if you're switching on the
size of the array).

--Jonathan