Generische binäre Suche in C#

Question

Unten ist meine generische binäre Suche. Es funktioniert mit dem Integer-Array (es findet alle Elemente darin). Aber das Problem tritt auf, wenn ich ein String-Array verwende, um irgendwelche String-Daten zu finden. Es läuft okay für die ersten Index- und letzten Indexelemente, aber ich kann die mittleren Elemente nicht finden.

Stringarray = new string[] { "b", "a", "ab", "abc", "c" }; 

public static void BinarySearch<T>(T[] array, T searchFor, Comparer<T> comparer) { 

     int high, low, mid; 
     high = array.Length - 1; 
     low = 0; 
     if (array[0].Equals(searchFor))    
      Console.WriteLine("Value {0} Found At Index {1}",array[0],0); 
     else if (array[high].Equals(searchFor)) 
      Console.WriteLine("Value {0} Found At Index {1}", array[high], high); 
     else 
     { 
      while (low <= high) 
      { 
       mid = (high + low)/2; 
       if (comparer.Compare(array[mid], searchFor) == 0) 
       { 
        Console.WriteLine("Value {0} Found At Index {1}", array[mid], mid); 
        break; 
       } 
       else 
       { 
        if (comparer.Compare(searchFor, array[mid]) > 0) 
         high = mid + 1; 
        else 
         low = mid + 1; 
       } 

      } 
      if (low > high) 
      { 
       Console.WriteLine("Value Not Found In the Collection"); 
      } 
     }     
    } 

Answer 1

Die beiden Linien sind verdächtig:

high = mid + 1 
low = mid + 1 

Hmm. Sehen Sie sich die Offsets an. Natürlich ist das gut dokumentiert Binary Search Algorithm auf Wikipedia. Sie machen auch zusätzliche Arbeit. Untersuchen Sie den Pseudocode und die Beispiele genau.

Answer 2

Eine binäre Suche erfordert, dass die Eingabe sortiert wird. Wie wird "b, a, ab, abc, c" sortiert? Es scheint nicht nach einem offensichtlichen Sortierschlüssel sortiert zu sein. Wenn Sie versuchen, unsortierte Daten zu durchsuchen, sollten Sie einen Hash-Satz verwenden, keine binäre Suche in einer Liste.

Auch Ihre Berechnung des Mittelpunkts ist subtil falsch, weil die Addition von high + low überlaufen kann. Es wird dann eine negative Zahl, die durch zwei geteilt wird.

Dies ist für Arrays mit realistischer Größe äußerst unwahrscheinlich, aber es ist durchaus möglich, dass Sie diesen Algorithmus eines Tages für Datentypen verwenden, die die Indexierung mit großen Ganzzahlen unterstützen, z. B. eine Speicherabbilddatei mit sortierten Daten.

Die beste Vorgehensweise zum Schreiben eines binären Suchalgorithmus ist (high - low)/2 + low bei der Berechnung des Mittelpunkts, da diese die ganze Zeit in Reichweite bleibt.

Answer 3

pst Ihr Rat hat wirklich funktioniert. :) Dieser Code funktioniert sowohl für int als auch für String.

public static int BinarySearch<T>(T[] array, T searchFor, Comparer<T> comparer) 
    { 
     int high, low, mid; 
     high = array.Length - 1; 
     low = 0; 
     if (array[0].Equals(searchFor)) 
      return 0; 
     else if (array[high].Equals(searchFor)) 
      return high; 
     else 
     { 
      while (low <= high) 
      {     
       mid = (high + low)/2; 
       if (comparer.Compare(array[mid], searchFor) == 0)     
        return mid;      
       else if (comparer.Compare(array[mid], searchFor) > 0)      
        high = mid - 1;      
       else      
        low = mid + 1;     
      } 
      return -1;     
     }     
    } 

Answer 4

// Binary Suche rekursive Methode

public void BinarySearch(int[] input,int key,int start,int end) 
    { 
     int index=-1; 
     int mid=(start+end)/2; 
     if (input[start] <= key && key <= input[end]) 
     { 
      if (key < input[mid]) 
       BinarySearch(input, key, start, mid); 
      else if (key > input[mid]) 
       BinarySearch(input, key, mid + 1, end); 
      else if (key == input[mid]) 
       index = mid; 
      if (index != -1) 
       Console.WriteLine("got it at " + index); 
     } 
    } 

    int[] input4 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
    BinarySearch(input4, 1, 0, 8);