W
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
