CODEWITHSUNDEEP
c++searchstd
jiawen
jiawen

Reputation: 1208

binary search a std:map

Using c++, if I have n integers in a std::map, is it possible to efficiently search the largest element that is smaller than k in std::map ?

For example I have {1, 3, 5, 6} and k is 4 the returned value should be 3

I know std::map can search in log(n), if the it is exact match.

Upvotes: 1

Views: 449

Answers (3)

Vlad from Moscow
Vlad from Moscow

Reputation: 310950

You can use method lower_bound. For example

#include <iostream>
#include <map>

int main() 
{
    std::map<int, int> m = { { 1, 0 }, { 3, 0 }, { 5, 0 }, { 6, 0 } };

    auto it = m.lower_bound( 4 );

    if ( it != m.begin() )
    {
        std::cout << ( --it )->first << std::endl;
    }

    return 0;
}

Upvotes: 3

Fred Larson
Fred Larson

Reputation: 62063

Look into std::map::lower_bound(). Note that it will return an exact match if there is one. std::set has this as well.

Upvotes: 2

Matteo Italia
Matteo Italia

Reputation: 126787

Use lower_bound and decrement the returned iterator by one.

Upvotes: 5

Related Questions