Suche BinarySearch Algo mit RUeckgabewert: Position

Raute50

MahlZeit!

Bin auf der SUche nach einem Binary Search Algorithmus, der die Position in einem sortierten vector<long> zurueckgibt ( falls etwas gefunden wird ) oder 0.
Der bis dato von mir gefundene binary_search(...) Algorithmus, gibt nur true/false zurueck, was mir nichts bringt. Habe bis dato lower_bound() benutzt, aber gemerkt, dass bei mehreren gleichen Werten nicht die selbe Position zurueckgegeben wird, als bei vergleichbarer Binaerer Suche ...

#50

camper

Raute50 schrieb:

MahlZeit!

Bin auf der SUche nach einem Binary Search Algorithmus, der die Position in einem sortierten vector<long> zurueckgibt ( falls etwas gefunden wird ) oder 0.
Der bis dato von mir gefundene binary_search(...) Algorithmus, gibt nur true/false zurueck, was mir nichts bringt. Habe bis dato lower_bound() benutzt, aber gemerkt, dass bei mehreren gleichen Werten nicht die selbe Position zurueckgegeben wird, als bei vergleichbarer Binaerer Suche ...

#50

was erwartest du? sofern zum vergleichswert äquvalente elemente im vektor existieren, wird lower_bound immer auf das erste und upper_bound immer auf das letzte+1 dieser äquivalenten elemente zeigen.

Raute50

camper schrieb:

Raute50 schrieb:

MahlZeit!

Bin auf der SUche nach einem Binary Search Algorithmus, der die Position in einem sortierten vector<long> zurueckgibt ( falls etwas gefunden wird ) oder 0.
Der bis dato von mir gefundene binary_search(...) Algorithmus, gibt nur true/false zurueck, was mir nichts bringt. Habe bis dato lower_bound() benutzt, aber gemerkt, dass bei mehreren gleichen Werten nicht die selbe Position zurueckgegeben wird, als bei vergleichbarer Binaerer Suche ...

#50

was erwartest du? sofern zum vergleichswert äquvalente elemente im vektor existieren, wird lower_bound immer auf das erste und upper_bound immer auf das letzte+1 dieser äquivalenten elemente zeigen.

Das haben wir dann auch schon herausgefunden! Urspruenglich sollten in dem vector auch keine Eintraege doppelt sein ... aber leider tritt das nun doch auf ...

Deine Aussage hilft mir aber leider ueberhaupt nicht weiter, denn ich suche immer noch nach einer Variante von binary search, die die Postion zurueck gibt.

Existiert denn soetwas schon ueberhaupt oder muss ich mir das selber schreiben ?!

GreetZ!

#50

CStoll

lower_bound() gibt doch die Position zurück, wäre also das richtige für dich.

(eventuell ist der vector auch der falsche Container für dich - schonmal über (multi)set nachgedacht?)

Jester

Huh? Du kannst Dir damit doch das erste und das letzte holen. Und zwar nen iterator dadrauf. Mit dem iterator kannste auch die Position bestimmen.
Wenn es doppelte Einträge gibt, dann ist "die Position" übrigens nicht sehr eindeutig.

Raute50

Jester schrieb:

Huh? Du kannst Dir damit doch das erste und das letzte holen. Und zwar nen iterator dadrauf. Mit dem iterator kannste auch die Position bestimmen.
Wenn es doppelte Einträge gibt, dann ist "die Position" übrigens nicht sehr eindeutig.

Das stimmt ... sorry dafuer .... !

Gute Idee mit den beiden _bound FUnktionen ! Werde es gleich mal vorschlagen ... ( sitze gerade mit mehreren an einem C++ Projekt ).

DIE POSITION ziehlt unseres Erachtens auf die Position ab, die durch binary search entdeckt wird. Es gibt eine vergleichbare Funktion die wir adaptieren sollen, die binary_search() heisst und eine Postition zurueck gibt ...

Sieht wohl so aus, als muessten wir selber Hand anlgegen ...

GreetZ!

#50

Werner Salomon

Es gibt 4 Algorithmen in der STL, die eine binäre Suche durchführen. Das sind
lower_bound, upper_bound, equal_range und binary_search
Nach Deiner Beschreibung kannst Du Dein Problem sowohl mit 'lower_bound' als auch mit 'equal_range' lösen.
Es kommt lediglich darauf an, wie man das jeweilige Ergebnis interpretiert.

Anbei ein Beispiel, welches die Anwendung zeigt:

#include <algorithm>
#include <iterator>     // std::distance
#include <iostream>
#include <vector>

using namespace std;

void searchPos1( int x, const std::vector< int >& v )
{
    vector< int >::const_iterator i = lower_bound( v.begin(), v.end(), x );
    if( i != v.end() && *i == x )
    {
        cout << x << " an Position " << distance( v.begin(), i ) << " gefunden" << endl;
    }
    else
    {
        cout << x << " nicht gefunden" << endl;
    }
}

void searchPos2( int x, const std::vector< int >& v )
{
    pair< vector< int >::const_iterator, vector< int >::const_iterator > ret 
        = equal_range( v.begin(), v.end(), x );
    if( distance( ret.first, ret.second ) > 0 )
    {
        cout << x << " an Position " << distance( v.begin(), ret.first ) << " gefunden" << endl;
    }
    else
    {
        cout << x << " nicht gefunden" << endl;
    }
}

int main()
{
    const int arr[] = { -4, 0, 7, 13, 89, 123, 123, 124, 300 };
    vector< int > v( arr, arr + sizeof(arr)/sizeof(*arr) );

    searchPos1( 123, v );  // mit lower_bound
    searchPos2( 123, v );  // mit equal_range
    searchPos1( 125, v );
    searchPos2( 125, v );
    return 0;
}

Gruß
Werner

Edit: #include <iterator> vergessen