Is there a built-in way to efficiently search a unique, sorted array in PowerShell?

Question

Does PowerShell have a built-in method for an optimized search for a specific value in a unique, sorted array or collection that returns the index of the found value in the searched collection? Or perhaps a built-in collection type that provides such a method?

I know it's a fairly simple process to efficiently find a specific value in a sorted array or collection, and I could write a function to do this myself, but I hate reinventing the wheel! However, my searches have only turned up page upon page describing how to sort unsorted data in PowerShell.

Here is my specific use case: I have a set of SQL query results in PowerShell object form that, because of the way the SQL script was written, I know is unique and sorted. I have another set of data, and I need to find matching values from that other set within the SQL results. I want to do this efficiently rather than just iteratively looping until a match is found, but I don't want to write custom logic for such a common task when there almost certainly has to be something already available in PowerShell for doing this.

Answer 1

Depending on the data type, both, Array and List<T> have their own BinarySearch method, optimized for searching in sorted collections. This method has a time complexity of O(log n).

$array = 50..100
[array]::BinarySearch($array, 75) # Index: 25

[System.Collections.Generic.List[int]] $list = 50..100
$list.BinarySearch(75) # Index: 25

References:

• https://learn.microsoft.com/en-us/dotnet/api/system.array.binarysearch?view=net-7.0
• https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.binarysearch?view=net-7.0

---

Bonus for anyone curious how these methods perform against a linear search algorithm O(n) time complexity such as IndexOf (tests available in my gists).

Results from the tests show the following average milliseconds to find the index of a value in collections with 10.485.761 items:

Test               Average RelativeSpeed
----               ------- -------------
List.BinarySearch     0.09 1x
Array.BinarySearch    0.15 1.67x
Array.IndexOf         3.63 40.33x
List.IndexOf          5.03 55.89x