Ein Problem in vielen binären Suchimplementierungen?

Wir wissen, dass der binäre Suchalgorithmus besser ist als der lineare Suchalgorithmus. Die zur Ausführung dieses Algorithmus erforderliche Zeit beträgt O(log n). Meistens gibt es jedoch einige Probleme mit dem implementierten Code. Betrachten wir eine binäre Suchalgorithmus-Funktion wie unten gezeigt –

Beispiel

int binarySearch(int array[], int start, int end, int key){
   if(start <= end){
      int mid = (start + end) /2); //mid location of the list
      if(array[mid] == key)
         return mid;
      if(array[mid] > key)
         return binarySearch(array, start, mid-1, key);
         return binarySearch(array, mid+1, end, key);
   }
   return -1;
}

Dieser Algorithmus funktioniert gut, bis er am Anfang und am Ende eine größere Zahl erreicht. Wenn (Start + Ende) den Wert 2³² - 1 überschreitet, kann nach dem Umschließen eine negative Zahl zurückgegeben werden. Da negative Zahlen nicht als Array-Indizes unterstützt werden, kann dies zu Problemen führen.

Um dieses Problem zu lösen, gibt es verschiedene Möglichkeiten.

Methode 1

int mid = start + ((end - start) / 2)

Die zweite Methode funktioniert nur in Java, da es in C oder C++ keinen >>>-Operator gibt.

Methode 2 (nur für Java)

int mid = (start + end) >>> 1

Da >>> in C oder C++ nicht unterstützt wird, können wir die folgende Methode verwenden.

Methode 3

int mid = ((unsigned int) low + (unsigned int) high) >> 1

Das obige ist der detaillierte Inhalt vonEin Problem in vielen binären Suchimplementierungen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!