VB.NET BinarySearch List

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.

BinarySearch method performance

Example

Note

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.

Program that uses BinarySearch on List: VB.NET

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

Performance optimization

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.

DictionaryLogo

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 List

Summary

The VB.NET programming language

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

VB.NET: Collections