C# - Binärsuchalgorithmus für benutzerdefinierte Klassen-String-Liste

Question

Im Grunde brauche ich Hilfe bei der Anpassung meines binären Suchalgorithmus, um mit meiner String-Liste zu arbeiten, wie unten gezeigt. Hinweis, ich muss einen geschriebenen binären Suchalgorithmus verwenden, keine Verwendung von eingebauten C# -Funktionen wie .BinarySearch.

Ich werde nun zeigen, wie Sie die Liste formatiert ist und die Liste selbst:

// This class formats the list, might be useful to know 

public class Demo 
{ 
    public string Col; 
    public string S1; 
    public string S2; 
    public string S3; 

    public override string ToString() 
    { 
     return string.Format("Col: {0}, S1: {1}, S2: {2}, S3: {3}", Col, S1, S2, S3); 
    } 
} 

// The list itself 

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

Die Liste bereits in alphabetischer Reihenfolge des ‚Col‘ String-Werte sortiert, also warum Blau ist erste und Gelb ist letzte. Der 'Col' ist der Teil der Liste, der durchsucht werden soll. Im Folgenden habe ich meine aktuelle Binärsuche eingefügt, die Int-Arrays durchsuchen kann.

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 brauche Hilfe bei der Anpassung meines BinarySearch-Algorithmus, um für die obige Liste zu arbeiten. Wenn ihr Fragen habt oder mehr von meinem Code sehen wollt, fragt einfach.

Answer 1

Konkrete Antwort: Anpassung Ihrer Methode für den speziellen Fall ist ziemlich einfach.

Lassen erste Update Ihrer bestehenden Verfahren eine allgemeinere Methode verwenden (IComparable<T>.CompareTo zum Vergleich anstelle der int Operatoren:

public static int BinarySearch_R(int key, int[] array, int low, int high) 
{ 
    if (low > high) return -1; 
    int mid = (low + high)/2; 
    int compare = key.CompareTo(array[mid]); 
    if (compare == 0) 
    { 
     return mid; 
    } 
    if (compare < 0) 
    { 
     return BinarySearch_R(key, array, low, mid - 1); 
    } 
    else { 
     return BinarySearch_R(key, array, mid + 1, high); 
    } 
} 

Dann alles, was Sie brauchen, ist die obige Methode kopieren/einfügen, ersetzen int key mit string key , int[] array mit List<Demo> array und array[mid] mit array[mid].Col:

public static int BinarySearch_R(string key, List<Demo> array, int low, int high) 
{ 
    if (low > high) return -1; 
    int mid = (low + high)/2; 
    int compare = key.CompareTo(array[mid].Col); 
    if (compare == 0) 
    { 
     return mid; 
    } 
    if (compare < 0) 
    { 
     return BinarySearch_R(key, array, low, mid - 1); 
    } 
    else { 
     return BinarySearch_R(key, array, mid + 1, high); 
    } 
} 

Erweiterte Antwort: Während Sie das oben beschriebene tun können, müssen Sie das Gleiche für jede andere Eigenschaft/Klasse tun, die Sie benötigen.

Ein viel besserer Ansatz wäre es, den Code zu verallgemeinern.

public static class MyAlgorithms 
{ 
    public static int BinarySearch<T, TKey>(this IReadOnlyList<T> source, Func<T, TKey> keySelector, TKey key, IComparer<TKey> keyComparer = null) 
    { 
     return source.BinarySearch(0, source.Count, keySelector, key, keyComparer); 
    } 

    public static int BinarySearch<T, TKey>(this IReadOnlyList<T> source, int start, int count, Func<T, TKey> keySelector, TKey key, IComparer<TKey> keyComparer = null) 
    { 
     // Argument validations skipped 
     if (keyComparer == null) keyComparer = Comparer<TKey>.Default; 
     int lo = start, hi = start + count - 1; 
     while (lo <= hi) 
     { 
      int mid = lo + (hi - lo)/2; 
      int compare = keyComparer.Compare(key, keySelector(source[mid])); 
      if (compare < 0) 
       hi = mid - 1; 
      else if (compare > 0) 
       lo = mid + 1; 
      else 
       return mid; 
     } 
     return -1; 
    } 
} 

Jetzt können Sie diese einzelne Methode für jede verwenden: Zum Beispiel int[] und List<Demo> als IReadOnlyList<T>, int/string key als TKey key, Demo.Col als Func<T, TKey>, CompareTo als IComparer<TKey>.Compare, so dass die endgültige generische Methode könnte so sein verallgemeinert werden Datenstruktur. Zum Beispiel sucht Ihre List<Demo> von Col so sein würde:

int index = list.BinarySearch(e => e.Col, "Red"); 

Answer 2

Ive getan nur die grundlegendsten Dinge in C#, so könnte dies nur völlig nutzlos. Ich hatte eine Aufgabe für CS 2-Klasse, wo es zumindest etwas ähnlich klingt wie Sie wollen, aber wir verwenden Java. Also gehe ich davon aus, dass du deine Liste von Gegenständen nach einem Stichwort sortiert haben möchtest ("Blau", "Grün" etc ...). Ich habe eine LinkedList verwendet, aber das spielt keine Rolle.

class Node { 
    String keyword; 
    LinkedList<String> records = new LinkedList<>(); 
    Node left; 
    Node right; 


    public Node(String keyword, LinkedList<String> records) { 
     this.keyword = keyword; 
     this.records = records; 
    } 
} 

Nun, der einzige wirkliche Unterschied mindestens i nach Nummern sortiert nach einem String und einer sortiert ein BST zwischen ist, dass Sie irgendeine Art von Vergleichsverfahren müssen sagen können, um zu sehen, ob ein Wort> oder < in Alphabet.Also hier ist, wie ich die Insert-Funktion hat:

/** 
* insert node 
* @param keyword compare it to other strings 
*/ 
public void insert(String keyword, LinkedList<String> records) { 
    //create a new Node 
    Node n = new Node(keyword, records); 
    int result; 
    Node current = root; 
    Node parent = null; 


    //cont. until NULL 
    while (current != null) { 
     result = current.keyword.compareTo(n.keyword); 
     if (result == 0) return; 
     else if (result > 0) { 
      parent = current; 
      current = current.left; 
     } 
     else if (result < 0) { 
      parent = current; 
      current = current.right; 
     } 
    } 

    if (parent == null) root = n; 
    else { 
     result = parent.keyword.compareTo(n.keyword); 
     if (result > 0) parent.left = n; 

     else if (result < 0) parent.right = n; 

    } 
} 

So ist die Methode "compareTo (...)" gibt 1 zurück, wenn der String höher in Alphabet 0, wenn gleiche und -1, wenn niedriger. Also würde ich, wenn ich überhaupt nahe an dem bin, was du fragst, die C# -Version dieser Methode bekommen und BST wie gewohnt implementieren.

Answer 3

Erstellen Sie einfach make-Klasse IComparable und erstellen Sie eine benutzerdefinierte CompareTo() -Methode. Die Standardmethoden wie sort funktionieren automatisch, sobald die Klasse IComparable erbt.

public class Demo : IComparable 
    { 
     public string Color; 
     public int value; 
     public Boolean truth; 


     public int CompareTo(Demo other) 
     { 
      int results = 0; 
      if (this.Color == other.Color) 
      { 
       if (this.value == other.value) 
       { 
        results = this.truth.CompareTo(other.truth); 
       } 
       else 
       { 
        results = this.value.CompareTo(other.value); 
       } 
      } 
      else 
      { 
       results = this.Color.CompareTo(other.Color); 
      } 

      return results; 
     }