Felix G
27.03.2010, 01:41
Hallo Leute,
nehmen wir mal eine einfache Implementierung einer binären Suche
int16_t binsearch(uint8_t key, uint8_t* data, int16_t size)
{
int16_t low = 0;
int16_t high = size;
int16_t index;
while (low < high)
{
index = low + ((high - low) >> 1);
if (data[index] < key)
low = index + 1;
else
high = index;
}
if ((low < size) && (data[low] == key))
return low;
else
return -1;
}Diese Funktion liefert, bei einem sortierten Array, immer den passenden Index zu "key" (wie man es eben von einer binären Suche erwartet).
Die Frage die ich mir stelle ist jetzt, wie ich diese Funktion derart erweitern kann, daß sie mir bei der Suche nach einem Wert der mehrfach im Array steht, den ersten und letzten passenden Index liefert.
nehmen wir mal eine einfache Implementierung einer binären Suche
int16_t binsearch(uint8_t key, uint8_t* data, int16_t size)
{
int16_t low = 0;
int16_t high = size;
int16_t index;
while (low < high)
{
index = low + ((high - low) >> 1);
if (data[index] < key)
low = index + 1;
else
high = index;
}
if ((low < size) && (data[low] == key))
return low;
else
return -1;
}Diese Funktion liefert, bei einem sortierten Array, immer den passenden Index zu "key" (wie man es eben von einer binären Suche erwartet).
Die Frage die ich mir stelle ist jetzt, wie ich diese Funktion derart erweitern kann, daß sie mir bei der Suche nach einem Wert der mehrfach im Array steht, den ersten und letzten passenden Index liefert.