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. Advertisements

  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. Advertisements

  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. Advertisements

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. Vivi Orunitia
    Replies:
    11
    Views:
    4,781
    Martijn Lievaart
    Feb 4, 2004
  2. Peter Jansson
    Replies:
    5
    Views:
    6,969
    Ivan Vecerina
    Mar 17, 2005
  3. Replies:
    6
    Views:
    944
    Jim Langston
    Oct 30, 2005
  4. Jason Heyes
    Replies:
    8
    Views:
    1,012
    Andrew Koenig
    Jan 15, 2006
  5. arunix

    binary_search

    arunix, Sep 1, 2009, in forum: C++
    Replies:
    6
    Views:
    538
    Jerry Coffin
    Sep 1, 2009
  6. Rune Allnor
    Replies:
    2
    Views:
    2,389
    Richard Herring
    Feb 1, 2010
  7. Angus
    Replies:
    10
    Views:
    1,143
    Jonathan Lee
    Mar 11, 2011
  8. Alf P. Steinbach
    Replies:
    5
    Views:
    295
    Jorgen Grahn
    Jan 1, 2014
Loading...