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

Question

PowerShell有没有内置的方法来优化搜索特定值在一个唯一、排序的数组或集合中，并返回找到的值在搜索集合中的索引？或者有没有内置的集合类型提供这样的方法？

我知道在一个排序的数组或集合中高效地找到特定值是一个相当简单的过程，我可以自己编写一个函数来实现这个功能，但我讨厌重复造轮子！然而，我的搜索只找到了一页又一页的描述如何在PowerShell中对未排序的数据进行排序。

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

- ornsio

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

---

对于任何对这些方法在与线性搜索算法（例如IndexOf）相比的时间复杂度O(n)感兴趣的人，我们提供奖金（测试结果可在我的代码片段中查看）。

测试结果显示，在包含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

- Santiago Squarzon

---

谢谢！"二分查找"显然是我正在寻找的术语，我只是忘记它叫什么了。 - undefined

Answer 2

另一种与索引无关且具有O(1)的查找复杂度的解决方案是哈希表。在Powershell中有一个内置类型可以实现这个功能。如果你的数据集已经有了唯一的键，你可以将其作为哈希表的键，并将数据作为值存储。作为额外的好处，哈希表不需要输入的数据进行排序。

举个例子，考虑一个虚构的数据集，如下所示，

# This would be your colums from SQL query
$dataset = @("1,a,b", "2,c,d", "3,e,f", "4,g,h", "10,aa,bb")
$ht = @{}

foreach($d in $dataset) {
    # Get unique id from 1st column for ht key
    $key = ($d -split ',')[0]
    # Add the whole row as data for the key
    $ht.Add($key, $d)
}

第一列用作哈希表的键。现在可以使用带有方括号的键访问哈希表，但要注意索引不是数字，而是字符串。就像这样，

$ht['10']
10,aa,bb

查找数据通过键是O(1)，但也可以通过值进行查找by value。这是O(n)，因为它是线性搜索。

$ht.ContainsKey('2')
True
$ht.ContainsValue('2,c,d')
True

- vonPryz

---

谢谢您的回复 - 这是一个很好的想法，但我希望避免将整个数据集重建为哈希表所带来的额外开销。由于源数据已经是唯一且排序的，我不确定这种开销是否值得，因为它已经可以通过O(log n)的效率进行搜索。 - undefined