Функция бинарного поиска

Delphi , Синтаксис , Память и Указатели

function FoundByBinarySearch(
  LowIdx,
  HighIdx: LongInt;
  var Result: LongInt;
  const GoalIs: CompareFunc;
  var Data;
  var Goal
  ): Boolean;
var
  CompVal: CompareResults;
begin
  FoundByBinarySearch := FALSE;

  if HighIdx < LowIdx then
    Exit;

  Result := LowIdx + ((HighIdx - LowIdx) div 2);
  CompVal := GoalIs(Result, Data, Goal);

  if CompVal = BinEqual then
    FoundByBinarySearch := TRUE
  else if (LowIdx < HighIdx) then
  begin
    if CompVal = BinLess then
      HighIdx := Result - 1
    else {CompVal = BinGreater}
      LowIdx := Result + 1;
    FoundByBinarySearch := FoundByBinarySearch(
      LowIdx, HighIdx, Result, GoalIs, Data, Goal)
  end
  else if (CompVal = BinLess) then
    Dec(Result)
end; { function FoundByBinarySearch }

Вот перевод текста на русский язык:

Это реализация алгоритма двоичного поиска в Pascal.

Подпись функции

function FoundByBinarySearch(
  LowIdx, HighIdx: LongInt;
  var Result: LongInt;
  const GoalIs: CompareFunc;
  var Data, Goal: ???): Boolean;

Функция принимает пять параметров:

1. LowIdx и HighIdx: диапазон индексов для поиска.
2. Result: переменная для хранения результата поиска.
3. GoalIs: функция обратного вызова, сравнивающая значение с цели (значения Data и Goal не определены здесь, но я предполагаю, что они будут переданы в виде аргументов).
4. Data и Goal: не определены в этом фрагменте кода, но, вероятно, это массив для поиска и целевое значение.

Тело функции

var
  CompVal: CompareResults;
begin
  FoundByBinarySearch := FALSE;

  if HighIdx < LowIdx then
    Exit;

  Result := LowIdx + ((HighIdx - LowIdx) div 2);
  CompVal := GoalIs(Result, Data, Goal);

  if CompVal = BinEqual then
    FoundByBinarySearch := TRUE
  else if (LowIdx < HighIdx) then
  begin
    if CompVal = BinLess then
      HighIdx := Result - 1
    else {CompVal = BinGreater}
      LowIdx := Result + 1;
    FoundByBinarySearch := FoundByBinarySearch(
      LowIdx, HighIdx, Result, GoalIs, Data, Goal)
  end
  else if (CompVal = BinLess) then
    Dec(Result);
end; {function FoundByBinarySearch}

Вот что функция делает:

1. Инициализируем FoundByBinarySearch в FALSE.
2. Проверяем, является ли диапазон поиска пустым (HighIdx < LowIdx). Если да, то выходим.
3. Вычисляем средний индекс диапазона с помощью целочисленного деления.
4. Сравниваем среднее значение с цели с помощью функции обратного вызова GoalIs. Храним результат в CompVal.
5. Если сравнениеyieldает точное совпадение (BinEqual), то устанавливаем FoundByBinarySearch в TRUE.
6. Если не, то корректируем диапазон поиска на основе результата сравнения:
   • Если среднее значение меньше цели (BinLess), то обновляем HighIdx до значения, которое на один меньше текущего Result.
   • Иначе, обновляем LowIdx до значения, которое на один больше текущего Result.
7. Вызываем рекурсивно функцию FoundByBinarySearch с обновленным диапазоном поиска.
8. Если сравнениеyieldает значение меньше цели (BinLess) и мы не в точном совпадении, то уменьшаем Result.

Замечания

• Код предполагает, что функция обратного вызова GoalIs возвращает enum-значение, представляющее результат сравнения: BinEqual, BinLess или BinGreater.
• Массив для поиска (Data) и целевое значение (Goal) не определены в этом фрагменте кода, поэтому вам нужно передать их в виде аргументов при вызове функции.
• Эта реализация использует рекурсивный подход. Если вы обеспокоены ошибками стека для больших данных, 考虑 использовать итеративный подход вместо этого.

Функция бинарного поиска - алгоритм для нахождения значения в отсортированном массиве, реализованный на примере функции FoundByBinarySearch, которая ищет целевое значение Goal в диапазоне LowIdx-HighIdx с помощью сравнения с элементами массива Data.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Память и Указатели ::