Бинарный поиск в целочисленном массиве

Delphi , Синтаксис , Массивы

Автор: Mystic
WEB-сайт: http://delphibase.endimus.com

{ **** UBPFD *********** by delphibase.endimus.com ****
>> Бинарный поиск

Бинарный поиск в целочисленном массиве - шаблон для функции,
выполняющей бинарный поиск.
X - значение, которое ищеться
A - массив в котором происходит поиск.
возвращаемое значение
индекс элемента, начиная с которого значения в массиве превышают заданное значение
в случае точного поиска заменить строку Result := L и -1 будет свидетельствовать
о том, что значение не найдено.

Зависимости: System
Автор:       Mystic, mystic2000@newmail.ru, ICQ:125905046, Харьков
Copyright:   Mystic
Дата:        25 апреля 2002 г.
***************************************************** }

function BinaryFind(X: Integer; A: array of Integer): Integer;

  function RecurceFind(L, R: Integer): Integer;
  var
    M: Integer;
  begin
    if R < L then
    begin
      Result := L; // Result := -1 если поиск точный
      Exit;
    end;
    M := (L + R) div 2;
    if A[M] = X then
    begin
      Result := M;
      Exit;
    end;
    if A[M] > X then
      Result := RecurceFind(L, M - 1)
    else
      Result := RecurceFind(M + 1, R)
  end;

begin
  Result := RecurceFind(Low(A), High(A));
end;

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

Это реализация алгоритма двоичного поиска в Delphi на языке Pascal. Функция BinaryFind ищет элемент X в массиве A и возвращает индекс элемента, если он существует, или индекс, где элементы в массиве начинают превышать значение X. Если точного совпадения не найдено, она возвращает индекс, где поиск должен продолжаться.

Разбивка кода:

1. Функция BinaryFind принимает два параметра: X, значение для поиска, и A, массив целых чисел.
2. Функция использует другой вложенный функцию, называемый RecurceFind. Это рекурсивная функция, которая выполняет двоичный поиск.
3. В функции RecurceFind:
   • Если диапазон [L, R] пуст (т.е. R < L), возвращается индекс L (или -1, если поиск является точным).
   • Вычисляется средний индекс M.
   • Если элемент на индексе M совпадает с X, возвращается M.
   • Если A[M] > X, рекурсивно вызывается RecurceFind с диапазоном [L, M-1]. Иначе, вызывается с диапазоном [M+1, R].
4. В основной части функции BinaryFind:
   • Вызывается RecurceFind с начальными значениями диапазона [Low(A), High(A)], где Low(A) и High(A) - функции, возвращающие наименьший и наибольший индексы массива соответственно.
   • Присваивается результат RecurceFind переменной Result.

Предложение альтернативного решения:

Вместо использования рекурсивной функции можно использовать реализацию двоичного поиска с использованием цикла. Это может быть более эффективно и проще для понимания для некоторых разработчиков.

Пример реализации:

function BinaryFind(X: Integer; A: array of Integer): Integer;
var
  L, R: Integer;
begin
  L := Low(A);
  R := High(A);

  while L <= R do
  begin
    var M := (L + R) div 2;
    if A[M] = X then
      Result := M
    else if A[M] > X then
      R := M - 1
    else
      L := M + 1;
  end;

  // Если элемент не найден, возвращается индекс, где поиск должен продолжаться
  Result := L;
end;

Эта реализация имеет тот же временной сложность (O(log n)) что и рекурсивная версия, но может быть более эффективной на практике из-за уменьшенного накладного времени.

Бинарный поиск в целочисленном массиве - функция, реализующая алгоритм бинарного поиска для нахождения индекса элемента, начиная с которого значения в массиве превышают заданное значение.

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

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

:: Главная :: Массивы ::