Бинарный поиск элемента в массиве

Бинарный поиск (binary search) - алгоритм поиска индекса элемента в упорядоченном массиве, в нем используется деление массива на половины, по это й причине алгоритм называют методом деления пополам.

Метод бинарного поиска достаточно прост для понимания, в то же время он очень эффективен. Поскольку на каждой итерации количество элементов в рабочей области массива уменьшается вдвое.

Описание алгоритма бинарного поиска

  • определяем значение элемента в средине рабочей области массива и сравниваем его с искомым;
  • если они равны, выводим значение;
  • если значение середины больше искомого то поиск продолжается в первой половине, иначе во второй;
  • проверяем не сошлись ли границы рабочей области, если да - искомого значения нет, нет - переходим на первый шаг.

Рекурсивная реализация бинарного поиска

{$CODEPAGE UTF8}
program BinSearch1;
const
  arrayLength = 15;
var
  sortedArray : array [1..arrayLength] of integer;
  i, k, index : integer;

function BinSearch(key, leftIndex, rightIndex : integer):integer;
var
  middleIndex : integer;
begin
  if leftIndex > rightIndex then
    BinSearch := -1
  else
    begin
      middleIndex := (leftIndex + rightIndex) div 2;
      if sortedArray[middleIndex] = key then
        begin
          BinSearch := middleIndex;
        end
      else
        begin
          if sortedArray[middleIndex] > key then
            BinSearch := BinSearch(key, leftIndex, middleIndex)       {рекурсивный вызов функции}
          else
            BinSearch := BinSearch(key, middleIndex + 1, rightIndex); {рекурсивный вызов функции}
        end;
    end;
end;

begin
  writeln('Исходный массив: ');
  {заполнение массива числами}
  for i := 1 to arrayLength do
  begin
    sortedArray[i] := i * 2;
    write(sortedArray[i]:4);
  end;
  writeln;
  write('Введите значение искомого элемента ');
  readln(k);

  index := BinSearch(k, 1, arrayLength);
  if index = -1 then
    writeln ('Элемент не найден')
  else
    writeln ('Индекс элемента в массиве ', index);
  readln;
end.

Итеративная реализация алгоритма бинарного поиска

{$CODEPAGE UTF8}
program BinSearch2;
const
  elementsCount = 15;
var
  sortedArr : array [1..elementsCount] of integer;
  i, key, res : integer;

function BinarySearch(key : integer):integer;
var
  firstIndex, midIndex, lastIndex: integer;
begin
  firstIndex := 1;
  lastIndex := elementsCount;
  while firstIndex < lastIndex do
    begin
      midIndex := (firstIndex + lastIndex) div 2;
      if sortedArr[midIndex] = key then
        begin
          BinarySearch := midIndex;
          Exit; {выход из процедуры если индекс найден}
        end
      else
        begin
          if sortedArr[midIndex] > key then
            lastIndex := midIndex
          else
            firstIndex := midIndex + 1;
        end;
    end;
  {сюда попадаем в случае если ничего не нашли}
  BinarySearch := -1;
end;

begin
  writeln('Исходный массив: ');
  for i := 1 to elementsCount do
  begin
    sortedArr[i] := i * 3;
    write(sortedArr[i]:4);
  end;
  writeln;
  write('k = ');
  readln(key);

  res := BinarySearch(key);
  if res = -1 then
    writeln ('Поиск завершен, элемент не найден')
  else
    writeln ('Индекс элемента в массиве ', res);
  readln;
end.

Смотрите также: