std::binary_search(), iterator to the found element and timecomplexity

Discussion in 'C++' started by Alex Vinokur, Jan 7, 2009.

  1. Alex Vinokur

    Alex Vinokur Guest

    Hi,

    std::binary_search() takes logarithmic time on (sorted) container, but
    returns bool, not iterator to the found element.

    std::find() returns iterator to the found element, but takes linear
    time.

    Is there any way to get iterator to the found element on sorted
    container in logarithmic time?

    Alex Vinokur
     
    Alex Vinokur, Jan 7, 2009
    #1
    1. Advertising

  2. Alex Vinokur schrieb:
    > Hi,
    >
    > std::binary_search() takes logarithmic time on (sorted) container, but
    > returns bool, not iterator to the found element.
    >
    > std::find() returns iterator to the found element, but takes linear
    > time.
    >
    > Is there any way to get iterator to the found element on sorted
    > container in logarithmic time?


    std::lower_bound, std::upper_bound, std::equal_range

    --
    Thomas
     
    Thomas J. Gritzan, Jan 7, 2009
    #2
    1. Advertising

  3. On Jan 7, 6:49 am, Alex Vinokur <> wrote:

    > std::binary_search() takes logarithmic time on (sorted) container, but
    > returns bool, not iterator to the found element.
    >
    > std::find() returns iterator to the found element, but takes linear
    > time.
    >
    > Is there any way to get iterator to the found element on sorted
    > container in logarithmic time?


    It is:

    template<class Iter, class T>
    Iter binary_search_iter(Iter begin, Iter end, T val)
    {
    Iter i = std::lower_bound(begin, end, val);
    return i != end && *i == val
    ? i // found
    : end // not found
    ;
    }

    --
    Max
     
    Maxim Yegorushkin, Jan 7, 2009
    #3
    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. Replies:
    6
    Views:
    698
    Jim Langston
    Oct 30, 2005
  2. arunix

    binary_search

    arunix, Sep 1, 2009, in forum: C++
    Replies:
    6
    Views:
    373
    Jerry Coffin
    Sep 1, 2009
  3. Angus
    Replies:
    10
    Views:
    955
    Jonathan Lee
    Mar 11, 2011
  4. Stefan Ram
    Replies:
    0
    Views:
    107
    Stefan Ram
    Dec 31, 2013
  5. Stefan Ram
    Replies:
    0
    Views:
    105
    Stefan Ram
    Dec 31, 2013
Loading...

Share This Page