Find position of element using binary_search

Discussion in 'C++' started by Angus, Mar 7, 2011.

  1. Angus

    Angus Guest

    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
     
    Angus, Mar 7, 2011
    #1
    1. Advertising

  2. On 7 mar, 12:59, Angus <> 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
     
    Michael Doubez, Mar 7, 2011
    #2
    1. Advertising

  3. Michael Doubez <> 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.)
     
    Juha Nieminen, Mar 9, 2011
    #3
  4. Angus

    Jonathan Lee Guest

    On Mar 9, 4:54 am, Juha Nieminen <> wrote:
    > Michael Doubez <> 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
     
    Jonathan Lee, Mar 9, 2011
    #4
  5. Angus

    James Kanze Guest

    On Mar 9, 10:54 am, Juha Nieminen <> wrote:
    > Michael Doubez <> 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, Mar 9, 2011
    #5
  6. Angus

    James Kanze Guest

    On Mar 9, 2:00 pm, Jonathan Lee <> wrote:
    > On Mar 9, 4:54 am, Juha Nieminen <> 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
     
    James Kanze, Mar 9, 2011
    #6
  7. Angus

    Jorgen Grahn Guest

    On Wed, 2011-03-09, James Kanze wrote:
    > On Mar 9, 2:00 pm, Jonathan Lee <> wrote:
    >> On Mar 9, 4:54 am, Juha Nieminen <> 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 .
     
    Jorgen Grahn, Mar 9, 2011
    #7
  8. James Kanze <> wrote:
    > On Mar 9, 2:00 pm, Jonathan Lee <> wrote:
    >> On Mar 9, 4:54 am, Juha Nieminen <> 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, Mar 10, 2011
    #8
  9. James Kanze <> 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).
     
    Juha Nieminen, Mar 10, 2011
    #9
  10. Angus

    James Kanze Guest

    On Mar 10, 8:00 am, Juha Nieminen <> wrote:
    > James Kanze <> 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
     
    James Kanze, Mar 10, 2011
    #10
  11. Angus

    Jonathan Lee Guest

    On Mar 9, 3:25 pm, James Kanze <> wrote:
    > On Mar 9, 2:00 pm, Jonathan Lee <> wrote:
    >
    > > On Mar 9, 4:54 am, Juha Nieminen <> 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


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

    --Jonathan
     
    Jonathan Lee, Mar 11, 2011
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alex Vinokur
    Replies:
    2
    Views:
    1,224
    Maxim Yegorushkin
    Jan 7, 2009
  2. arunix

    binary_search

    arunix, Sep 1, 2009, in forum: C++
    Replies:
    6
    Views:
    347
    Jerry Coffin
    Sep 1, 2009
  3. Stefan Ram
    Replies:
    0
    Views:
    94
    Stefan Ram
    Dec 31, 2013
  4. Stefan Ram
    Replies:
    0
    Views:
    97
    Stefan Ram
    Dec 31, 2013
  5. Alf P. Steinbach
    Replies:
    5
    Views:
    135
    Jorgen Grahn
    Jan 1, 2014
Loading...

Share This Page