二分查找所有出现的？(BinarySearch for all occurrences?)

我如何可以搜索一个阵列使用值的所有出现BinarySearch ？默认TArray.BinarySearch在System.Generics.Collections只返回一个索引。

例如阵列：

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

Answer 1:

二进制搜索假定您已经有了数组排序，所以任何其他匹配的元素会被返回的匹配元件周围聚集的BinarySearch 。德尔福XE5帮助指出，

如果在阵列等于项目在一个以上的元件中，第一匹配的索引FoundIndex被返回。这是任何相匹配的项目并不一定是第一个项目，索引“。

这表明你需要向前和向后运行阵列中的搜索，获得的所有匹配的元素。

Answer 2:

让我来解释这个问题有点多给你。一旦你找到一个索引顺序搜索和二进制搜索的区别取决于你希望找到的数据类型。 10000元是不相关的，如何在项目的许多不同的值，你正在寻找的。举例来说，如果我有只包含1,2,3,4和5，我们正在谈论的情况下可能会有成千上万的每个值等一系列后续的二进制搜索将是可取的10000个元素的列表。如果值的范围可以从1〜1000000，我们不太可能有重复和二进制搜索，随后在两个方向顺序搜索是最好的办法。

对于二进制文件，然后顺序的方法，算法找到起点和终点指标是以下几点：

查找使用二进制搜索索引。
搜索左边找到使用顺序搜索的第一个索引。
搜索右边找到使用顺序搜索的最后一个索引。

如果你想使用二进制搜索，那么你就需要切换你的方法，做了一系列的递归搜索，直到找到起点和终点。

查找使用二进制搜索索引。
二进制搜索1 ..（指数-1）的值。
如果你觉得值，那么你将需要1和newindex-1之间重新搜索。
您将需要重复此搜索，直到你没有找到任何有价值的多。
二进制搜索（索引+ 1）..端的值。
如果您发现价值，那么你将需要移到newIndex + 1和端之间重新搜索。
您将需要重复此搜索，直到你没有找到任何有价值的多。

一个代码示例看起来有点像这样。此代码是为退出时，第一次找到匹配的二进制搜索。

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;

最终，你的数据（我们没有），将决定你的行动最好的办法。

现在使事情变得复杂一点。德尔福在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;

这工作，因为搜索也返回即使它没有在数组中找到安勤+ 1的下一个值的指数。在if在最后陈述时，我们的价值也是数组的最后一个值来处理这种情况。

这是依赖于TArray.BinarySearch剩下的，因为它是代码。