Um in einem einfachen sortierten Feld schnell etwas zu finden ist die binäre Suche (Binary search) das ideale Instrument. Statt wie die lineare Suche jedes Element in einem Feld mit dem Suchbegriff zu vergleichen, teilt sie das Feld immer wieder in zwei Hälften und sucht in der Hälfte weiter, die das Element enthalten muss. Durch dieses Vorgehen braucht die binäre Suche in einem Feld mit 60000 Elementen maximal 17 Vergleiche um das gesuchte Element zu finden oder um festzustellen, daß das Element nicht in dem Feld enthalten ist.

Die hier vorgestellte C++ Variante bietet zwei Besonderheiten. Zum einen arbeitet sie iterativ, obwohl die Standardimplementierung in der Regel rekursiv erfolgt. Die iterative Variante hat aber den Vorteil den Stack zu schonen. Zum zweiten liefert sie bei Bedarf einen Index, um die Einfügeposition für ein nicht vorhandenes Element festzustellen.

/*
** Binaere Suche
** Sucht in einem Array mit Strings nach einem String.
** Ergebnis ist die Adresse des gesuchten Strings im
** Array oder NULL wenn der String nicht gefunden wurde.
*/

char* binarySearch(
  char** strlist,   // Array mit Strings
  int    listlen,   // Laenge des Arrays
  char*  str,       // Suchstring
  int*   index      // Index des Suchstrings oder
                     // Einfuegeposition wenn nicht
                     // vorhanden
)
{
  // Linke Grenze
  int left = 0;
  // Rechte Grenze
  int right = listlen - 1;

  int cmp,cmpIndex;

  while(1)
  {
   // nicht gefunden
   if(right < left)
   {
     // Indexausgabe gewuenscht
     if(index != NULL)
     {
       // Einfuegeposition
       *index = right;
     }
     return NULL;
   }
   // Vergleichsindex ist in der Mitte
   // von linker und rechter Grenze
   cmpIndex = (left + right) / 2;
   // Werte vergleichen
   cmp = strcmp(strlist[cmpIndex], str);
   // gefunden
   if(cmp==0)
   {
     // Indexausgabe gewuenscht
     if(index != NULL)
     {
       // Fundposition
       *index = cmpIndex;
     }
     return strlist[cmpIndex];
   }
   // str > strlist[ cmpIndex ]
   else if(cmp < 0)
   {
     // in der rechten Haelfte weitersuchen
     left = cmpIndex + 1;
   }
   // str < strlist[ cmpIndex ]
   else
   {
     // in der linken Haelfte weitersuchen
     right = cmpIndex - 1;
   }
  }
}