.NET Array Class File String Sub ArrayList Cast Console DataTable DateTime Dictionary Enum For If IndexOf Interface Lambda LINQ List Nothing Parse Process Property Regex Replace Select Sort Split StringBuilder Substring
BinarySearch is an optimized search Function. It requires that the List instance is already sorted. It hones in on the value by dividing the number of elements being searched several times. It provides better performance on sorted Lists.
This example program adds three Strings to the List instance. The List is then sorted with the Sort Function. It is important to Sort here. If you use an unsorted List, BinarySearch will give negative indexes that are incorrect.
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
As I have progressed with programming, I have realized that methods like BinarySearch are not that useful. Instead, hashtables such as Dictionary are the best for fast lookups. In my programs, I usually just use Dictionary for all lookups.Dictionary
BinarySearch is faster than IndexOf on large sorted Lists. This is true except when the element you are searching for comes near the start. IndexOf is then faster because it is simpler.
The C# version of this article found that BinarySearch becomes much faster than linear loops after around 100 elements are searched. Again, this performance is pathetic when compared to Dictionary.
And:The IndexOf method is always faster when your searched-for element is at the start.BinarySearch
This article looked at the BinarySearch method on the List type. There is a narrow use case for BinarySearch. If performance is critical, a hashed lookup is superior. If elements are not sorted, IndexOf is required.
However:On sorted Lists where performance is not critical but merely nice to have, BinarySearch has its place.List