BinarySearch是否所有出现？ [英] BinarySearch for all occurrences?

问题描述

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

How can I search for all occurrences of a value in an array using BinarySearch? The default TArray.BinarySearch in System.Generics.Collections only returns one index.

示例数组：

A = [1、2、3、3、3、6、7， 8、9];

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

推荐答案

让我向您多解释一下这个问题。找到索引后，顺序搜索和二进制搜索之间的区别取决于您希望找到的数据类型。 10000个元素无关紧要，您要搜索的项目有多少个不同的值。例如，如果我有10000个仅由1,2、3、4和5组成的元素的列表，那么我们正在谈论一种情况，其中每个值可能有数千个，因此最好进行一系列后续的二进制搜索。如果值的范围在1到1000000之间，则我们重复的可能性将大大降低，最好的方法是二进制搜索，然后在两个方向上依次搜索。

Let me explain the problem a bit more to you. The difference between a sequential search and a binary search once you have found an index depends on the type of data you expect to find. The 10000 elements is not relevant, how many different values of the item you are searching for is. For example, if I had a list of 10000 elements consisting of only 1,2,3,4 and 5. We are talking about a situation where there could be thousands of each value and a series of subsequent binary searches would be preferable. If the values could range from 1 to 1000000, we are far less likely to have duplicates and a binary search followed by a sequential search in both directions is the best approach.

对于二进制然后顺序的方法，查找起始索引和终止索引的算法如下：

For the binary and then sequential approach, the algorithm to find the start and end index would be the following:

1. 使用二进制查找索引


2. 向左搜索以使用顺序搜索找到第一个索引。


3. 向右搜索以使用顺序搜索找到最后一个索引。

如果要使用二进制搜索，则需要切换方法并进行一系列递归搜索，直到找到开始和结束为止

If you wanted to use binary searches then you would need to switch your approach and do a series of recursive searches until you find the start and finish.

1. 使用二进制搜索查找索引。


2. 二进制搜索1 ..（index- 1）作为值。


3. 如果找到该值，则需要在1和newindex-1之间再次搜索。


4. 您将需要重复此搜索，直到您不再找到该值。


5. 二进位搜索（index + 1）.. end取值。


6. 如果找到该值那么您将需要在newindex + 1和end之间再次搜索。


7. 您将需要重复此搜索，直到找不到值为止。

1. Find the index using a binary search.
2. Binary search 1..(index-1) for the value.
3. If you find the value then you will need to search again between 1 and newindex-1.
4. You will need to repeat this search until you don't find the value any more.
5. Binary search (index+1)..end for the value.
6. If you find the value then you will need to search again between newindex+1 and end.
7. You will need to repeat this search until you don't find the value any more.

一个代码示例看起来像这样。

A code example would look a bit like this. This code is for a binary search that exits when it first finds a match.

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;

最终，您的数据（我们没有）将为您确定最佳的解决方案

Ultimately, your data (which we don't have) will determine the best course of action for you.

现在要使事情复杂一些。 Delphi在TArray中使用的二进制搜索的一种变体。BinarySearch不会在找到匹配项后尽早结束。

Now to complicate things a bit. The variation of the binary search that Delphi is using in TArray.BinarySearch is one that doesn't end early when a match is found. It will always find the index of the first item as it doesn't exit the loop when it finds a match.

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;

这意味着当您拥有很多相同的值时，您会受到一点惩罚有很好的副作用。您可以执行以下操作找到所需的内容：

That means that you have a bit of a penalty when you have a lot of identical values but it does have a nice side effect. You can do something like this to find what you are looking for:

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;

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

This works because the search also returns the index of the next value even if it doesn't find aValue + 1 in the array. The if statement at the end is to handle the case when our value is also the last value of the array.

这取决于TArray.BinarySearch的代码是否保持不变。

This is dependent on the code for TArray.BinarySearch remaining as it is.

这篇关于BinarySearch是否所有出现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！