lower bound Suche

Hallo,

angenommen, ihr habt eine sortierte Liste mit Zahlen. Ihr wollt suchen, ob eine bestimmte Zahl vorkommt und wenn ja, an welcher Stelle diese vorkommt. Kommt die gesuchte Zahl mehrfach vor, so ist der kleinste Index gesucht.
Also genau das, was in C++ lower_bound macht.

Meine Idee war nun, die Binärsuche zu verwenden.
Allerdings mit einer kleinen Änderung: auch wenn ein passender Wert gefunden wird, wird weitergesucht, denn vielleicht gibt es ja noch ein besseres Ergebnis. Das Ergebnis wird aber trotzdem gespeichert.
Fällt euch eine andere/bessere Lösung ein?

Hab meine Idee mal schnell in C runtergetippt damit das jetzt nicht so theoretisch klingt:

int arr[]={0,1,2,2,2,2,2,2,2,2,3,3,3,4,4,5};
	int len=sizeof(arr)/sizeof(int);
	int search=2;
	int l=0,r=len-1,m=0;
	int found=0;
	int lowest=0;

	while(l<=r)
	{
		m=(l+r)/2;

		if(arr[m]<search)
		{
			l=m+1;
		}

		if(arr[m]>search)
		{
			r=m-1;		
		}

		// passendes Element: Position merken, aber weiterprobieren für noch besseres Element
		if(arr[m]==search)
		{
			found=1;
			lowest=m;
			r=m-1;			
		}
	}

	if(found)
	{
		printf("Wert %d gefunden an Stelle %d\n",search,lowest);
	}

Binary search macht man am besten nur mit halboffenen Intervallen. Anstatt den Übergang von <=search zu >search zu suchen, ist es besser, den Übergang von <search zu >=search zu suchen. Dann hat man in r das erste Element, das >=search ist. Das macht die Schleife viel einfacher:

...
int l=0,r=len,m=0; // len statt len-1
...

while(r-l > 1)
{
    m=(l+r)/2;

    if(arr[m]<search)
        l=m;
    else
        r=m;
}

found=r<len && arr[r]==search;
lowest=r;

if(found)
{
    printf("Wert %d gefunden an Stelle %d\n",search,lowest);
}

SeppJ

edit: Dein Vergleich mit lower_bound hat mich verwirrt. Suchst du nun die kleinste Zahl, auf die ein Kriterium zutrifft oder suchst du tatsächlich nur gleiche Zahlen (was ist, wenn es keine gleiche Zahl gibt?)? Die folgende Antwort habe ich geschrieben unter der Annahme, dass du so etwas wie lower_bound suchst:

An deiner Version stört mich eine große Sache: Du schreibst der Gleichheit eine Sonderbedeutung zu, die gar nicht da ist. Gesucht ist doch das erste Element, das nicht kleiner ist als der Referenzwert. Dies und nur dies ist dein Kriterium (weiterhin ist gar nicht klar, ob überhaupt == oder > sinnvoll definiert sind, aber das kann man leicht ausbessern). Wenn wir also ein Element finden, das kleiner ist als der Vergleichswert, können wir guten Gewissens weiter voranschreiten. Wenn wir eines finden, das nicht kleiner ist, dann müssen wir unseren Suchschritt (binäre Suche ist schon die richtige Idee) etwas verkleinern. Wenn der Suchschritt bereits minimal ist (also 0), dann sind wir beim gesuchten Element.

cplusplus.com gibt eine Beispielimplementierung für std::lower_bound, meine Lösung sähe auch nicht viel anders aus:

template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}

Dies setzt ziemlich genau das um, was ich oben beschrieben habe.

danke.
@SeppJ: du hast die Frage richtig interpretiert, ich hab tatsächlich gemeint, bei mehreren gleichen Zahlen hintereinander das erste passende Element zu finden.

1 2 2 2 3 4
  ^
  |