BinarySearch in generischer Liste Eine von List<T> abgeleitete Klasse, die Elemente sortiert verwaltet und bei der Suche nach Elementen die Binarysearch-Methode nutzt.
Autor:   Manfred Bohn	Bewertung:     [ Jetzt bewerten ]	Views:  8.045
ohne Homepage	System:  Win7, Win8, Win10, Win11	kein Beispielprojekt

Geben Sie hier Ihre persönliche Bewertung ab! Anzahl Bewertungen bisher: 4 Bewertung insgesamt: mittelmäßig Durchschnittliche Bewertung: 2.0 von 5 Sternen

sehr gut     gut     nützlich     mittelmäßig     mangelhaft

Bei einer generischen Liste (Namespace: System.Collections.Generic) stehen die Methoden "Contains" und "IndexOf" zur Verfügung, um zu prüfen, ob ein bestimmtes Element bereits in der Liste vorhanden ist.

Ist für die Listen-Elemente die Schnittstelle "IComparable<T>" (und dementsprechend die Schnittstelle "IEquatable<T>") implementiert, kann die Liste nach dem Hinzufügen aller Elemente durch die "Sort"-Methode (ansteigend) sortiert werden. Danach steht die "BinarySearch"-Methode zur Verfügung, die bei der Suche in langen Listen wesentlich effizienter arbeitet (ab etwa 200 Einträgen), als "IndexOf" (O[log(n)] statt O[n]-Operation).

Umfasst die Liste eine Länge von 1000 Elementen, ist die binäre Suche nach einem Element etwa 4x schneller als die lineare Suche, bei 500.000 Elementen ist die binäre Suche bereits mehr als 600x schneller.

Die Binärsuch-Methode der generischen Liste erkennt NICHT, ob die Listen-Elemente tatsächlich sortiert worden sind und liefert gegebenenfalls unbrauchbare Resultate!
Liegt ein zu suchendes Element in der Liste mehrfach vor, liefert die "BinarySearch"-Methode NICHT den niedrigsten Index, sondern 'irgendeinen' der zugehörigen Indices.

Bei sortierten Listen, denen dynamisch Elemente hinzugefügt werden, ist es zweckmäßiger, die Elemente bereits bei der Zuweisung an der korrekten Sortier-Position einzufügen. Die "BinarySearch"-Methode unterstützt diese Operation:
Wenn List<T> den angegebenen Wert nicht enthält, gibt die Methode eine negative ganze Zahl zurück. Auf diese negative ganze Zahl können Sie die bitweise Komplementoperation (~) anwenden, um den Index des ersten Elements abzurufen, das größer als der Suchwert ist. Beim Einfügen des Werts in die List<T> sollte dieser Index als Einfügemarke verwendet werden, um die Sortierreihenfolge beizubehalten(MSDN-Dokumentation).

Die Klasse "sList" ist von der generischen Liste abgeleitet. Sie verwaltet die Elemente in ansteigend sortierter Reihenfolge unter Nutzung der "BinarySearch"-Methode. Die oben angegebenen Besonderheiten der "BinarySearch"-Methode sind bei der Implementierung berücksichtigt worden.

Eine Überladung des Konstruktors übernimmt eine Auflistung von Items, die direkt in die neu erstellte "sList"-Instanz eingetragen und anschließend sortiert wird. Das ist der effizienteste Weg, um eine Instanz der "sList"-Klasse zu erstellen, die eine große Anzahl von Items enthält.

Die "Add"- und die "Addrange"-Methode fügen Elemente in eine Instanz der "sList" ein. Dabei wird der Listenindex der Elemente durch die Implementierung der "IComparable"-Schnittstelle per "BinarySearch" ermittelt.
Die direkte Zuweisung eines Items auf einen bestimmten Index ist oder das Einfügen ist nicht möglich. Die Default-Eigenschaft der Klasse ist deshalb ReadOnly.

Die"Contains"-Methode und die Überladungen der "IndexOf"-Methode verwenden "BinarySearch" für die schnelle Suche nach einem Element - ab einer Listen-Länge von 200 Elementen. Bei kurzen Listen ist die Verwendung der linearen Suche effizienter. "IndexOf" gibt den Index des ersten Vorkommens, "LastIndexOf" den Index des letzten Vorkommens eines Elements in der Liste zurück. Die Rückgabewerte dieser Methoden entsprechen auch bei binärer Suche denen der Basisklasse.

Die "Frequency"-Methode gibt die Häufigkeit eines Elements in der Liste an. Fehlt das abgefragte Element in der Liste, wird 0 zurückgegeben.

Zum Entfernen von Elementen werden die Überladungen der "Remove"-Methode der Basisklasse herangezogen.

Methoden der generischen Liste, welche die Reihenfolge der Elemente ändern würden ("Insert", "Sort", "Reverse"), sind bei der "sList"-Klasse nicht implementiert ("Shadows"). Aufrufe dieser Methoden lösen jeweils die "Not Implemented"-Ausnahme aus.

Bei der Erstellung von Klassen, deren Instanzen als Elemente einer "sList"-Klasse fungieren, sollte darauf geachtet werden, daß die in der "CompareTo"-Methode verwendeten Eigenschaften nur im Klassen-Konstruktor zugewiesen werden können, weil bei einer nachträglichen Änderung die Reihenfolge in der "sList" eventuell nicht mehr korrekt ist.

Option Strict On
Option Explicit On
Option Infer Off
 
Imports System.Collections.Generic
 
''' <summary>Verwaltung einer sortierten Liste unter Verwendung von BinarySearch</summary>
''' <typeparam name="T">Datentyp der Elemente (IEquatable, IComparable muß implementiert sein)</typeparam>
Public Class SList(Of T As {IEquatable(Of T), IComparable(Of T)})
  Inherits List(Of T)
 
  ''' <summary>minimale Listenlänge, ab der die binäre Suche eingesetzt wird</summary>
  Private Const critlength As Integer = 200
 
#Region "Konstruktoren"
  ''' <summary>Erstellt eine neue Instanz, die über die Standardkapazität verfügt</summary>
  Public Sub New()
    MyBase.new()
  End Sub
 
  ''' <summary>Erstellt eine neue Instanz mit vorgegebener Anfangs-Kapazität</summary>
  ''' <param name="capacity">anfängliche Anzahl von Elementen</param>
  Public Sub New(ByVal capacity As Integer)
    MyBase.new(capacity)
  End Sub
 
  ''' <summary>Erstellt eine neue Instanz, die die Elemente der Auflistung sortiert enthält</summary>
  ''' <param name="collection">einzutragende Elemente der Auflistung</param>
  Public Sub New(collection As IEnumerable(Of T))
    MyBase.New(collection)
    MyBase.Sort()
  End Sub
#End Region
 
#Region "Add-/Addrange"
  ''' <summary>Fügt ein Objekt in die sortierte Liste ein</summary>
  ''' <param name="item">einzufügendes Objekt</param>
  Public Shadows Sub Add(ByVal item As T)
    ' Einfügung (oder Anhängen) des Items durch Nutzung von "Binarysearch"
    MyBase.Insert(FindListIndex(item), item)
  End Sub
 
  ''' <summary>Fügt eine Auflistung von Objekten in die sortierte Liste ein</summary>
  ''' <param name="items">Auflistung der einzufügenden Objekte</param>
  Public Shadows Sub AddRange(ByVal items As IEnumerable(Of T))
    If items Is Nothing Then Exit Sub
    For Each item As T In items
      ' Einfügung durch Add-Methode (BinarySearch)
      Me.Add(item)
      Next item
  End Sub
 
  ''' <summary>Ruft das Element am angegebenen Index ab</summary>
  ''' <param name="Index">Der nullbasierte Index des Elements, das abgerufen werden soll</param>
  Default Public Shadows ReadOnly Property Item(ByVal Index As Integer) As T
    Get
      Return MyBase.Item(Index)
    End Get
   End Property
#End Region
 
#Region "Contains, Indexof, LastIndexOf"
  ''' <summary>Bestimmt, ob sich ein Element in der sortierten Liste befindet?</summary>
  ''' <param name="item">das zu suchende Objekt</param>
  ''' <returns>Objekt in der sortierten Liste vorhanden?</returns>
  Public Shadows Function Contains(ByVal item As T) As Boolean
    If MyBase.Count < critlength Then
      Return MyBase.Contains(item)
    Else
      Return MyBase.BinarySearch(item) >= 0
    End If
  End Function
 
  ''' <summary>Gibt den niedrigsten Index eines Elements in der 
  ''' sortierten Liste zurück (oder -1)</summary>
  ''' <param name="item">das zu suchende Objekt</param>
  ''' <returns>niedrigster Index des gesuchten Objekts in der Liste (oder -1)</returns>
  Public Shadows Function IndexOf(ByVal item As T) As Integer
    If MyBase.Count < critlength Then
      Return MyBase.IndexOf(item)
    Else
      Dim bs_indx As Integer = MyBase.BinarySearch(item)
      If bs_indx < 0 Then Return -1
      Return FirstItemIndex(bs_indx)
    End If
  End Function
 
  ''' <summary>Gibt den niedrigsten Index eines Elements in einem Bereich 
  ''' der sortierten Liste zurück (oder -1)</summary>
  ''' <param name="item">das zu suchende Objekt</param>
  ''' <param name="index">nullbasierter Startindex des zu durchsuchenden Bereichs</param>
  ''' <returns>niedrigster Index des gesuchten Objekts im Bereich der Liste (oder -1)</returns>
  Public Shadows Function IndexOf(ByVal item As T, ByVal index As Integer) As Integer
    If MyBase.Count < critlength Then
      Return MyBase.IndexOf(item, index)
    Else
      Dim count As Integer = MyBase.Count - index
      Dim bs_indx As Integer = MyBase.BinarySearch(index, count, item, Nothing)
      If bs_indx < 0 Then Return -1
      Return FirstItemIndex(bs_indx, index)
    End If
  End Function
 
  ''' <summary>Gibt den niedrigsten Index eines Elements in einem Bereich der sortierten 
  ''' Liste zurück (oder -1)</summary>
  ''' <param name="item">das zu suchende Objekt</param>
  ''' <param name="index">nullbasierter Startindex des zu durchsuchenden Bereichs</param>
  ''' <param name="count">Länge des zu durchsuchenden Bereichs der Liste</param>
  ''' <returns>niedrigster Index des gesuchten Objekts im Bereich der Liste (oder -1)</returns>
  Public Shadows Function IndexOf(ByVal item As T, ByVal index As Integer, _
    count As Integer) As Integer
 
    If MyBase.Count < critlength Then
      Return MyBase.IndexOf(item, index, count)
    Else
      Dim bs_indx As Integer = MyBase.BinarySearch(index, count, item, Nothing)
      If bs_indx < 0 Then Return -1
      Return FirstItemIndex(bs_indx, index)
    End If
  End Function
 
  ''' <summary>Gibt den höchsten Index eines Elements in der sortierten Liste 
  ''' zurück (oder -1)</summary>
  ''' <param name="item">das zu suchende Objekt</param>
  ''' <returns>höchster Index des gesuchten Objekts in der Liste (oder -1)</returns>
  Public Shadows Function LastIndexOf(ByVal Item As T) As Integer
    If MyBase.Count < critlength Then
      Return MyBase.LastIndexOf(Item)
    Else
      Dim bs_indx As Integer = MyBase.BinarySearch(Item)
      If bs_indx < 0 Then Return -1
      Return LastItemIndex(bs_indx)
    End If
  End Function
 
  ''' <summary>Gibt den höchsten Index eines Elements in einem Bereich der 
  ''' sortierten Liste zurück (oder -1)</summary>
  ''' <param name="item">das zu suchende Objekt</param>
  ''' <param name="index">nullbasierter Startindex des zu durchsuchenden 
  ''' Bereichs (Rückwärtssuche)</param>
  ''' <returns>höchster Index des gesuchten Objekts im Bereich der Liste (oder -1)</returns>
  Public Shadows Function LastIndexOf(ByVal item As T, ByVal index As Integer) As Integer
    If MyBase.Count < critlength Then
      Return MyBase.LastIndexOf(item, index)
    Else
      Dim count As Integer = MyBase.Count - index
      Dim bs_indx As Integer = MyBase.BinarySearch(0, index + 1, item, Nothing)
      If bs_indx < 0 Then Return -1
      Return LastItemIndex(bs_indx, index)
    End If
  End Function
 
  ''' <summary>Gibt den höchsten Index eines Elements in einem Bereich der 
  ''' sortierten Liste zurück (oder -1)</summary>
  ''' <param name="item">das zu suchende Objekt</param>
  ''' <param name="index">nullbasierter Startindex des zu durchsuchenden 
  ''' Bereichs (Rückwärtssuche)</param>
  ''' <param name="count">Länge des zu durchsuchenden Bereichs der Liste</param>
  ''' <returns>höchster Index des gesuchten Objekts im Bereich der Liste (oder -1)</returns>
  Public Shadows Function LastIndexOf(ByVal item As T, ByVal index As Integer, _
    count As Integer) As Integer
 
    If MyBase.Count < critlength Then
      Return MyBase.LastIndexOf(item, index, count)
    Else
      Dim bs_indx As Integer = MyBase.BinarySearch(index - count + 1, count, item, Nothing)
      If bs_indx < 0 Then Return -1
      Return LastItemIndex(bs_indx, index)
    End If
  End Function
 
  ''' <summary>Bestimmung der Häufigkeit eines Items in der sortierten Liste</summary>
  ''' <param name="item">das zu suchende Objekt</param>
  ''' <returns>Häufigkeit des Objekts (ggf. 0)</returns>
  Public Function Frequency(ByVal item As T) As Integer
    Dim firstindex As Integer = IndexOf(item)
    If firstindex = -1 Then Return 0
    Dim lastindex As Integer = LastItemIndex(firstindex)
    Return lastindex - firstindex + 1
  End Function
#End Region
 
#Region "Helpers"
  Private Function FindListIndex(ByVal item As T) As Integer
    ' binäre Suche nach einem Listen-Index zu einem Item
    Dim index As Integer = MyBase.BinarySearch(item)
    If index < 0 Then
      ' ersetzt die bitweise Komplement-Operation
      index = Math.Abs(index) - 1
    End If
    Return index
  End Function
 
  Private Function FirstItemIndex(ByVal index As Integer,
    Optional ByVal limitindex As Integer = 0) As Integer
 
    ' Bestimmung des niedrigsten Listenindex zu einem Item (ab Index bis Limitindex)
    ' Lineare Suche / Abschnitt gleicher Items (CompareTo=0)
    Dim item As T = MyBase.Item(index)
    Do
      index -= 1
    Loop While index >= limitindex AndAlso MyBase.Item(index).CompareTo(item) = 0
    Return index + 1
  End Function
 
  Private Function LastItemIndex(ByVal index As Integer, _
    Optional ByVal limitindex As Integer = -1) As Integer
 
    ' Bestimmung des höchsten Listenindex zu einem Item (ab Index bis Limitindex)
    ' Lineare Suche / Abschnitt gleicher Items (CompareTo=0)
    Dim item As T = MyBase.Item(index)
    If limitindex = -1 Then limitindex = Me.Count - 1
    Do
      index += 1
    Loop While index <= limitindex AndAlso MyBase.Item(index).CompareTo(item) = 0
    Return index - 1
  End Function
#End Region
 
#Region "Nicht implementiert"
  ''' <summary>nicht implementiert</summary>
  Public Shadows Sub Insert(ByVal index As Integer, ByVal element As T)
    Throw New NotImplementedException("Insert not implemented")
  End Sub
 
  ''' <summary>nicht implementiert</summary>
  Public Shadows Sub InsertRange(ByVal index As Integer, ByVal items As IEnumerable(Of T))
    Throw New NotImplementedException("InsertRange not implemented")
  End Sub
 
  ''' <summary>nicht implementiert</summary>
  Public Shadows Sub Sort()
    Throw New NotImplementedException("Sort not implemented")
  End Sub
 
  ''' <summary>nicht implementiert</summary>
  Public Shadows Sub Sort(comparer As IComparer(Of T))
    Throw New NotImplementedException("SortByComparer not implemented")
  End Sub
 
  ''' <summary>nicht implementiert</summary>
  Public Shadows Sub Sort(comparison As System.Comparison(Of T))
    Throw New NotImplementedException("SortByComparison not implemented")
  End Sub
 
  ''' <summary>nicht implementiert</summary>
  Public Shadows Sub Sort(ByVal index As Integer, ByVal count As Integer, _
    ByVal comparer As IComparer(Of T))
 
    Throw New NotImplementedException("SortByComparer not implemented")
  End Sub
 
  ''' <summary>nicht implementiert</summary>
  Public Shadows Sub Reverse()
    Throw New NotImplementedException("Reverse not implemented")
  End Sub
#End Region
End Class