List BinarySearch
This page was last reviewed on Dec 8, 2022.
Dot Net Perls
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 Module
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.
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 tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
No updates found for this page.
© 2007-2024 Sam Allen.