是否有一种内置方法可以在 PowerShell 中有效搜索唯一的排序数组？

Question

PowerShell 是否具有内置方法来优化搜索唯一的排序数组或集合中的特定值，并返回搜索集合中找到的值的索引？或者也许是提供这种方法的内置集合类型？

我知道在排序数组或集合中有效查找特定值是一个相当简单的过程，我可以自己编写一个函数来执行此操作，但我讨厌重新发明轮子！然而，我的搜索只是一页一页地描述如何在 PowerShell 中对未排序的数据进行排序。

这是我的具体用例：我有一组 PowerShell 对象形式的 SQL 查询结果，由于 SQL 脚本的编写方式，我知道它们是唯一的且已排序。我有另一组数据，我需要在 SQL 结果中从另一组数据中找到匹配的值。我希望高效地执行此操作，而不仅仅是迭代循环直到找到匹配项，但我不想为此类常见任务编写自定义逻辑，因为几乎可以肯定 PowerShell 中已经有可用的东西来执行此操作。

Answer 1

根据数据类型，两者Array都有List<T>自己的BinarySearch方法，针对排序集合中的搜索进行了优化。该方法的时间复杂度为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

参考：

• 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

对于任何好奇这些方法如何针对线性搜索算法O( n)时间复杂度（例如（我的要点IndexOf中提供的测试））执行的人来说，这是一个奖励。

测试结果显示，在包含 10.485.761 个项目的集合中查找某个值的索引所需的平均毫秒数如下：

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