BinarySearch List. BinarySearch is an optimized search Function. It requires that the List instance is already sorted. It provides better performance on sorted Lists.
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.
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 Module2
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.
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.
Dot Net Perls is a collection of pages with code examples, which are updated to stay current. Programming is an art, and it can be learned from examples.
Donate to this site to help offset the costs of running the server. Sites like this will cease to exist if there is no financial support for them.
Sam Allen is passionate about computer languages, and he maintains 100% of the material available on this website. He hopes it makes the world a nicer place.