Бінарний пошук елемента в масиві

Бінарний пошук (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.

Дивіться також: