Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Find position of element using binary_search (http://www.velocityreviews.com/forums/t744720-find-position-of-element-using-binary_search.html)

 Angus 03-07-2011 11:59 AM

Find position of element using binary_search

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 03-07-2011 12:15 PM

Re: Find position of element using binary_search

On 7 mar, 12:59, Angus <anguscom...@gmail.com> wrote:
> * *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).

--
Michael

 Juha Nieminen 03-09-2011 10:54 AM

Re: Find position of element using binary_search

Michael Doubez <michael.doubez@free.fr> wrote:
> 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 03-09-2011 02:00 PM

Re: Find position of element using binary_search

On Mar 9, 4:54*am, Juha Nieminen <nos...@thanks.invalid> wrote:
> Michael Doubez <michael.dou...@free.fr> wrote:
> > 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.)

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 03-09-2011 09:22 PM

Re: Find position of element using binary_search

On Mar 9, 10:54 am, Juha Nieminen <nos...@thanks.invalid> wrote:
> Michael Doubez <michael.dou...@free.fr> wrote:
> > 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?

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

 James Kanze 03-09-2011 09:25 PM

Re: Find position of element using binary_search

On Mar 9, 2:00 pm, Jonathan Lee <jonathan.lee....@gmail.com> wrote:
> On Mar 9, 4:54 am, Juha Nieminen <nos...@thanks.invalid> 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.

--
James Kanze

 Jorgen Grahn 03-09-2011 10:12 PM

Re: Find position of element using binary_search

On Wed, 2011-03-09, James Kanze wrote:
> On Mar 9, 2:00 pm, Jonathan Lee <jonathan.lee....@gmail.com> wrote:
>> On Mar 9, 4:54 am, Juha Nieminen <nos...@thanks.invalid> 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 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

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

 Juha Nieminen 03-10-2011 07:55 AM

Re: Find position of element using binary_search

James Kanze <james.kanze@gmail.com> wrote:
> On Mar 9, 2:00 pm, Jonathan Lee <jonathan.lee....@gmail.com> wrote:
>> On Mar 9, 4:54 am, Juha Nieminen <nos...@thanks.invalid> 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.

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 03-10-2011 08:00 AM

Re: Find position of element using binary_search

James Kanze <james.kanze@gmail.com> wrote:
> 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 03-10-2011 08:54 PM

Re: Find position of element using binary_search

On Mar 10, 8:00 am, Juha Nieminen <nos...@thanks.invalid> wrote:
> James Kanze <james.ka...@gmail.com> wrote:
> > 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.

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.

--
James Kanze

All times are GMT. The time now is 06:21 AM.