HomeSearch

VB.NET BinarySearch List

Use the BinarySearch function on the List type to search a sorted list.
BinarySearch List. BinarySearch is an optimized search Function. It requires that the List instance is already sorted. It provides better performance on sorted Lists.ListSort
Notes, algorithm. This method hones in on the value by dividing the number of elements being searched several times. It can speed up searches in some real-world programs.
An example. This example program adds 3 Strings to the List instance. The List is then sorted with the Sort Function. It is important to Sort here.

Warning: If you use an unsorted List, BinarySearch will give negative indexes that are incorrect.

Info: BinarySearch finds the correct indexes. The sorted List contains "cat" at position 0. It contains "mouse" at position 1.

And: It contains "zebra" in the final position 2. If you run BinarySearch with an unsorted List, results are invalid.

VB.NET program that uses BinarySearch on List Module Module1 Sub Main() Dim animals As List(Of String) = New List(Of String) animals.Add("zebra") animals.Add("mouse") animals.Add("cat") ' This is required! animals.Sort() Dim zebraPosition As Integer = animals.BinarySearch("zebra") Dim catPosition As Integer = animals.BinarySearch("cat") Console.WriteLine(zebraPosition) Console.WriteLine(catPosition) End Sub End Module Output 2 0
Performance. In many programs, it is better to use Dictionary for lookups. The hashing mechanism in a Dictionary provides good performance for many real-world programs.Dictionary

Info: We do not discuss the algorithmic performance of binary search in depth here.

Important: Binary search is rarely needed in real-world programs. But it has an important use case on large sorted Lists.

Performance, IndexOf. BinarySearch is faster than IndexOf on large sorted Lists. But sometimes we know where an element may occur—we can then use IndexOf to reduce searching time.

Tip: If an element comes near the start, IndexOf will perform better than BinarySearch.

A summary. There is an important use case for BinarySearch. If performance is critical, a hashed lookup is often superior. And if elements are not sorted, IndexOf is required.
© 2007-2020 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
Home
Dot Net Perls