1

如何使用 搜索数组中所有出现的值BinarySearch？默认只返回一个索引TArray.BinarySearch。System.Generics.Collections

示例数组：

A = [1, 2, 3, 3, 3, 6, 7, 8, 9]；

4

2 回答 2

3

二进制搜索假定您已经对数组进行了排序，因此任何其他匹配元素都将聚集在BinarySearch. Delphi XE5 有助于指出

如果数组中有多个元素等于 Item，则在 FoundIndex 中返回第一个匹配项的索引。这是任何匹配项的索引，不一定是第一项。”

这表明您需要在数组中向前和向后运行搜索以获取所有匹配的元素。

于 2014-07-05T10:34:31.903 回答
3

让我再向你解释一下这个问题。找到索引后，顺序搜索和二分搜索之间的区别取决于您希望找到的数据类型。10000 个元素无关紧要，您要搜索的项目有多少不同的值。例如，如果我有一个仅包含 1、2、3、4 和 5 的 10000 个元素的列表。我们谈论的是每个值可能有数千个的情况，并且一系列后续的二进制搜索会更好。如果值的范围可以从 1 到 1000000，那么我们出现重复的可能性就小得多，并且二分查找然后在两个方向上进行顺序查找是最好的方法。

对于二进制然后顺序方法，查找开始和结束索引的算法如下：

  1. 使用二进制搜索查找索引。
  2. 向左搜索以使用顺序搜索找到第一个索引。
  3. 搜索权以使用顺序搜索查找最后一个索引。

如果你想使用二分搜索，那么你需要改变你的方法并进行一系列递归搜索，直到找到开始和结束。

  1. 使用二进制搜索查找索引。
  2. 二进制搜索 1..(index-1) 的值。
  3. 如果找到该值，则需要在 1 和 newindex-1 之间再次搜索。
  4. 您将需要重复此搜索，直到您不再找到该值。
  5. 二进制搜索 (index+1)..end 的值。
  6. 如果找到该值，则需要在 newindex+1 和 end 之间再次搜索。
  7. 您将需要重复此搜索，直到您不再找到该值。

代码示例看起来有点像这样。此代码用于在首次找到匹配项时退出的二进制搜索。

function GetIndexes(const aSearch: TSearchIntegers; const aValue: Integer; var aStartIndex, aEndIndex: Integer): Boolean;
var
  foundIndex: Integer;
  lookFor: Integer;
begin
  if BinarySearch(aSearch, aValue, foundIndex) then
  begin
    Result := True;
    lookFor := foundIndex;
    repeat
      aStartIndex := lookFor;
    until not BinarySearch(aSearch, aValue, lookFor, TComparer<Integer>.Default, 1, aStartIndex - 1);
    lookFor := foundIndex;
    repeat
      aEndIndex := lookFor;
    until not BinarySearch(aSearch, aValue, lookFor, TComparer<Integer>.Default, aEndIndex + 1, High(aSearch) - aEndIndex);
  end
  else
    Result := False;
end;

最终，您的数据（我们没有）将决定最适合您的行动方案。

现在让事情复杂一点。Delphi 在 TArray.BinarySearch 中使用的二进制搜索的变体是在找到匹配项时不会提前结束的变体。它总是会找到第一项的索引，因为它在找到匹配项时不会退出循环。

Result := False;
L := Index;
H := Index + Count - 1;
while L <= H do
begin
  mid := L + (H - L) shr 1;
  cmp := Comparer.Compare(Values[mid], Item);
  if cmp < 0 then
    L := mid + 1
  else
  begin
    H := mid - 1;
    if cmp = 0 then
      Result := True;  // <-- It doesn't end here
  end;
end;

这意味着当你有很多相同的值时你会受到一些惩罚，但它确实有一个很好的副作用。您可以执行以下操作来查找您要查找的内容：

function GetIndexes(const aSearch: TSearchIntegers; const aValue: Integer; var aStartIndex, aEndIndex: Integer): Boolean;
begin
  Result := False;
  if TArray.BinarySearch<Integer>(aSearch, aValue, aStartIndex) then
  begin
    TArray.BinarySearch<Integer>(aSearch, aValue+1, aEndIndex);
    if aSearch[aEndIndex] <> aValue then
      Dec(aEndIndex);
    Result := True;
  end;
end;

这是有效的，因为即使在数组中没有找到 aValue + 1 ，搜索也会返回下一个值的索引。最后的if语句是处理当我们的值也是数组的最后一个值的情况。

这取决于保持原样的 TArray.BinarySearch 代码。

于 2014-07-06T06:37:44.673 回答