C# - Binäre Suchzeichenkette

Question

Ich baue gerade eine Konsolenanwendung, die verschiedene Arten von Daten suchen und sortieren kann. Wie die Frage suggeriert; Ich brauche Hilfe bei der Erstellung eines binären Suchalgorithmus für eine String-Liste. Ich muss darauf hinweisen,, dass ich die integrierten C# -Funktionen wie list.binarysearch nicht verwenden kann, muss der Algorithmus von Grund auf neu programmiert werden. Außerdem enthält die Liste mehrere Elemente mit demselben Zeichenfolgenwert, so dass ich auch alle diese Elemente finden muss. Ich habe die Liste bereits in alphabetischer Reihenfolge sortiert, daher werde ich Algorthims verwenden, um die Ober- und Untergrenzen des zu suchenden Zeichenfolgenwerts zu finden.

Ich werde beginnen, indem ich zeige, wie ich die Liste formatiert habe.

var list = new List<Demo> 
     { 
      new Demo {Col = "Blue", S1 ="88", S2 ="Yes"}, 
      new Demo {Col = "Green", S1 ="43", S2 ="Yes"}, 
      new Demo {Col = "Green", S1 ="216", S2 ="No"}, 
      new Demo {Col = "Yellow", S1 ="100", S2 ="No"} 
     }; 

Die Liste wurde in alphabetischer Reihenfolge der Col-Werte sortiert. Die Liste ist eigentlich viel größer als das, aber Sie bekommen die Idee. Die binäre Suche muss alle "Col" -Werte suchen und einen bestimmten String-Wert finden.

Im Folgenden werde ich meinen binären Suchalgorithmus zeigen, der auf int-Arrays funktioniert.

public static int BinarySearch_R(int key, int[] array, int low, int high) 
    { 
     if (low > high) return -1; 
     int mid = (low + high)/2; 
     if (key == array[mid]) 
     { 

      return mid; 
     } 
     if (key < array[mid]) { 
      return BinarySearch_R(key, array, low, mid - 1); 
     } else { 
      return BinarySearch_R(key, array, mid + 1, high); 
     } 
    } 

Ich möchte diesen Algorithmus für meine obige Liste anpassen.

Schließlich zeige ich Ihnen den Code für die Suche der oberen und unteren Grenzen.

public static int lower_bound(int key, int[] arr , int low, int high) 
    { 
     if (low > high) 
      //return -1; 
      return low; 

     int mid = low + ((high - low) >> 1); 
     //if (arr[mid] == key) return mid; 

     //Attention here, we go left for lower_bound when meeting equal values 
     if (arr[mid] >= key) 
      return lower_bound(key, arr, low, mid - 1); 
     else 
      return lower_bound(key, arr, mid + 1, high); 
    } 

public static int upper_bound(int key, int[] arr, int low, int high) 
    { 
     if (low > high) 
      //return -1; 
      return low; 

     int mid = low + ((high - low) >> 1); 
     //if (arr[mid] == key) return mid; 

     //Attention here, we go right for upper_bound when meeting equal values 
     if (arr[mid] > key) 
      return upper_bound(key, arr, low, mid - 1); 
     else 
      return upper_bound(key, arr, mid + 1, high); 
    } 

Ich weiß, dass ich gefragt habe, für viele so auch getan werden, wenn Sie nur einen Teil des Problems helfen, ich dankbar sein werde. Wenn Sie weitere Informationen oder Code benötigen, fragen Sie einfach.

Answer 1

Zunächst möchte ich darauf hinweisen, dass Sie ein Array in Ihre Funktion übergeben. Also, warum benutzt du die Liste?

Auch wenn ich weiß, funktioniert Binärsuche nur, wenn ein Array sortiert ist. Also, würde ich vorschlagen, sortieren Sie Ihre Liste vorher. Obwohl ich keine Lösung finden kann, um Ihre benutzerdefinierte Liste zu durchsuchen (mit binärer Suche), auch nach dem Sortieren.

Ich hoffe, diese Punkte werden Ihnen helfen. Vielleicht kennst du sie schon. Ich bin neu bei StackOverflow, also lassen Sie mich bitte wissen, ob meine Antwort Ihnen geholfen hat oder nicht.