Задачи / Поиск / Двоичный (бинарный) поиск

Двоичный (бинарный) поиск: блок-схема и алгоритм

Массив должен быть отсортирован. Сравниваем x с серединой отрезка: если x меньше — ищем в левой половине, если больше — в правой. Каждый шаг уменьшает отрезок вдвое.

Алгоритм по шагам

Ввести отсортированный массив a и x; L = 1, R = n.
Пока L ≤ R: найти середину m = (L + R) div 2.
Если a[m] = x — найдено; если a[m] < x — L = m + 1; иначе R = m − 1.
Если отрезок стал пустым — элемента нет.

Открыть блок-схему в редакторе

Пример работы

Вход	a = [2, 5, 8, 12, 16, 23, 38], x = 23
Шаг 1	L = 1, R = 7: m = 4, a[4] = 12 < 23 → L = 5
Шаг 2	L = 5, R = 7: m = 6, a[6] = 23 — найдено
Результат	найден, номер 6

Решение на Python

n = int(input())
a = list(map(int, input().split()))  # отсортирован
x = int(input())
L, R, k = 0, n - 1, -1
while L <= R and k == -1:
    m = (L + R) // 2
    if a[m] == x:
        k = m
    elif a[m] < x:
        L = m + 1
    else:
        R = m - 1
print("найден, номер", k + 1 if k >= 0 else "не найден")

Решение на Pascal

var a: array[1..100] of integer;
    n, i, x, L, R, m, k: integer;
begin
  readln(n);
  for i := 1 to n do read(a[i]);
  readln(x);
  L := 1; R := n; k := 0;
  while (L <= R) and (k = 0) do
  begin
    m := (L + R) div 2;
    if a[m] = x then k := m
    else if a[m] < x then L := m + 1
    else R := m - 1;
  end;
  if k > 0 then writeln('найден, номер ', k)
  else writeln('не найден');
end.

Код блок-схемы

Схема выше нарисована по этому псевдокоду. Скопируйте его в редактор блок-схем или нажмите «Открыть блок-схему в редакторе».

блок-схема: Двоичный поиск
начало
ввод n, массив a[1..n], x
L = 1
R = n
k = 0
пока L ≤ R и k = 0
    m = (L + R) div 2
    если a[m] = x
        k = m
    иначе если a[m] < x
        L = m + 1
    иначе
        R = m − 1
если k > 0
    вывод «найден, номер», k
иначе
    вывод «не найден»
конец

Сложность

O(log n): для миллиона элементов нужно не больше 20 сравнений. Требование — отсортированный массив.

Частые ошибки

Применять к неотсортированному массиву — результат будет случайным.
Писать L = m или R = m вместо m ± 1 — возможен бесконечный цикл.
Условие L < R вместо L ≤ R — теряется случай, когда искомый элемент последний оставшийся.