std::lower_bound



  • Hi,

    wie funktioniert lower_bound? ich moechte den nach naechst kleineren oder gleichen key suchen...

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    auto find_next_smaller(const vector<int> &vec, const int key) {
        auto it = std::lower_bound(vec.begin(), vec.end(), key);
        if (it != vec.begin()) {
        	if (*it > key) {
          		it--;
        	}
          	return *it;
        }
    
        return *it;
    }
    
    int main() {
        vector<int> a;
        a.push_back(1);
        a.push_back(5);
        a.push_back(6);
    
        for (int i = 0; i <= 7; i++) {
        	cout << "i=" << i << ": " << find_next_smaller(a, i) << endl;
        }
    
        return 0;
    }
    

    ausgabe:

    i=0: 1
    i=1: 1
    i=2: 1
    i=3: 1
    i=4: 1
    i=5: 5
    i=6: 6
    i=7: 0 <--- warum 0, sollte 6 sein...?
    

    LG



  • http://en.cppreference.com/w/cpp/algorithm/lower_bound

    Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value.

    Da du kein element >=7 hast, ist die range leer und std::lower_bound gibt a.end() zurück, das heißt du greifst gerade auf ein element ausserhalb des vectors zu - und was das gibt ist undefiniertes Verhalten.



  • Die elegantere Lösung wäre wohl, von rbegin() nach rend() zu laufen und operator> als Vergleichsoperator zu wählen.



  • da meine sequenz sortiert ist koennte ich eine modifizierte binary search implementieren? gibt es schon sowas in der STL?



  • dein code ist fast richtig, du must nur den fall abfangen, dass lower_bound dir end zurückgibt.

    auto find_next_smaller(const vector<int> &vec, const int key) {
        auto it = std::lower_bound(vec.begin(), vec.end(), key);
        if (it == vec.end()) 
            return vec.back();
        if (it != vec.begin() && *it > key) {
            it--;
        }
        return *it;
    }
    


  • @otze: danke! nimmt lower_bound eine binary search wenn der vector sortiert ist?

    #include <iostream> 
    #include <vector> 
    #include <algorithm> 
    using namespace std; 
    
    auto find_next_smaller(const vector<int> &vec, const int key) { 
        auto it = std::lower_bound(vec.begin(), vec.end(), key); 
        if (it != vec.begin()) { 
            if (*it > key) { 
                it--; 
            } 
            return *it; 
        }
        else if (it == vec.end()) { 
        	it = vec.rbegin().base();
        }
    
        return *it; 
    } 
    
    int main() { 
        vector<int> a; 
        a.push_back(1); 
        a.push_back(5); 
        a.push_back(6); 
    
        for (int i = 0; i <= 7; i++) { 
            cout << "i=" << i << ": " << find_next_smaller(a, i) << endl; 
        } 
    
        return 0; 
    }
    


  • siehe die referenz: lower_bound hat garantierte komplexität O(log(n)) -> ja

    //edit dein Code ist genau falsch rum! im ersten if zweig geht er rein weil end!= begin



  • otze schrieb:

    dein code ist fast richtig, du must nur den fall abfangen, dass lower_bound dir end zurückgibt.

    auto find_next_smaller(const vector<int> &vec, const int key) {
        auto it = std::lower_bound(vec.begin(), vec.end(), key);
        if (it == vec.end()) 
            return vec.back();
        if (it != vec.begin() && *it > key) {
            it--;
        }
        return *it;
    }
    

    Und den Fall, dass vec leer ist. Und den Fall, dass key kleiner als alle Elemente von vec ist. Es erscheint mir schlauer, einen Iterator zurückzugeben.



  • ok.

    wie kann ich folgendes verwenden? ich weiss es gibt std::less...

    auto my_less = (auto &lhs, auto &rhs) -> bool {
        return lhs < rhs;
    };
    
    auto it = std::lower_bound(vec.begin(), vec.end(), key, my_less);
    


  • there we go:

    auto my_less = [](const auto &lhs, const auto &rhs) -> bool {
        	return lhs < rhs;
    };
    

    hat dieser generic Lambda einen nachteil?



  • so gehts auch:

    auto find_next_smaller(const vector<int> &vec, const int key) { 
        auto my_less = [&key](const auto &rhs) -> bool { 
            return key <= rhs; 
    	};
        auto it = std::find_if(vec.begin(), vec.end(), my_less);
        if (it == vec.end()) { 
            it = (vec.rbegin()+1).base();
        } 
    
        return *it; 
    }
    


  • newbieeee1 schrieb:

    so gehts auch:

    auto find_next_smaller(const vector<int> &vec, const int key) { 
        auto my_less = [&key](const auto &rhs) -> bool { 
            return key <= rhs; 
    	};
        auto it = std::find_if(vec.begin(), vec.end(), my_less);
        if (it == vec.end()) { 
            it = (vec.rbegin()+1).base();
        } 
        
        return *it; 
    }
    

    Was auch immer du unter "Gehen" verstehst... find_next_smaller({1,5},4) liefert 5 zurück.



  • @m.e.: ich gehe davon aus das der vector sortiert ist 🙂



  • {1,5} ist sortiert. Ganz abgesehen von den ganzen Spezialfällen, die du immer noch nicht behandelst. Aber ich wiederhole mich.


Anmelden zum Antworten