BinarySearch是否存在所有事件？

Question

如何使用BinarySearch搜索數組中所有值的出現？ System.Generics.Collections中的默認TArray.BinarySearch只返回一個索引。

例陣列：

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

Answer 1

二分法搜索假定您已經對數組進行了排序，因此任何其他匹配元素都將圍繞由BinarySearch返回的匹配元素聚簇。 Delphi XE5有助於說明

如果數組中有多個元素等於Item，則第一個匹配的索引將在FoundIndex中返回。這是任何相匹配的項目並不一定是第一個項目，索引「。

這表明你需要向前運行搜索和陣列得到所有匹配的元素中落後。

Answer 2

讓我再向你解釋一下這個問題，一旦你找到了一個索引，順序搜索和二分搜索的區別取決於你期望找到的數據的類型，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）..結束該值。
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; 

最終，您的數據（我們沒有）會爲您確定最佳的行動方案。

現在讓事情變得複雜一點。德爾福在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的代碼保持原樣。