BinarySearch для всех вхождений?

Бинарный поиск предполагает, что вы уже отсортировали свой массив, поэтому любые другие совпадающие элементы будут сгруппированы вокруг совпадающего элемента, возвращаемого BinarySearch. Справка Delphi XE5 отмечает, что

Если в массиве есть более одного элемента, равного Item, индекс первого совпадения возвращается в FoundIndex. Это индекс любого из совпадающих элементов, не обязательно первого элемента».

Это говорит о том, что вам нужно будет выполнить поиск как вперед, так и назад в массиве, чтобы получить все совпадающие элементы.

Позвольте мне объяснить вам проблему немного подробнее. Разница между последовательным поиском и бинарным поиском после того, как вы нашли индекс, зависит от типа данных, которые вы ожидаете найти. 10000 элементов не имеют значения, сколько разных значений искомого элемента. Например, если бы у меня был список из 10000 элементов, состоящий только из 1,2,3,4 и 5. Мы говорим о ситуации, когда каждого значения могут быть тысячи и предпочтительнее будет серия последовательных бинарных переборов. Если бы значения могли варьироваться от 1 до 1000000, у нас было бы гораздо меньше шансов иметь дубликаты, а бинарный поиск с последующим последовательным поиском в обоих направлениях — лучший подход.

Для двоичного, а затем последовательного подхода алгоритм поиска начального и конечного индекса будет следующим:

1. Найдите индекс с помощью бинарного поиска.
2. Поиск слева, чтобы найти первый индекс, используя последовательный поиск.
3. Поиск справа, чтобы найти последний индекс, используя последовательный поиск.

Если вы хотите использовать бинарный поиск, вам нужно будет изменить свой подход и выполнить серию рекурсивных поисков, пока не найдете начало и конец.

1. Найдите индекс с помощью бинарного поиска.
2. Бинарный поиск 1..(index-1) для значения.
3. Если вы найдете значение, вам нужно будет снова выполнить поиск между 1 и newindex-1.
4. Вам нужно будет повторять этот поиск, пока вы больше не найдете значение.
5. Двоичный поиск (индекс+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;

В конечном итоге ваши данные (которых у нас нет) определят для вас наилучший план действий.

Теперь немного усложним. Разновидность бинарного поиска, которую 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, оставшегося без изменений.