Двоичный (бинарный) поиск, BinSearch, БинПоиск

BinSearch

Поиск в упорядоченном массиве за $O(\log{n})$. Так же его называют - метод деления пополам и дихотомия (деление пополам по-гречески).

Перед применением двоичного поиска нужно отсортировать массив одним из алгоритмов сортировки.

Цель

Найти элемент со значением $x$ в отсортированном массиве $A$ из $N$ элементов или установить, что элемента $x$ в массиве $A$ нет.

Идея

Разделить отсортированный массив на две половины, сравнить средний элемент с $x$, понять в какой половине массива может находиться значение $x$ и перейти к поиску в этой половине.. И так далее, пока размер массива не уменьшиться до 1 элемента, тогда либо этот элемент равен $x$ и мы нашли $x$, либо не равен $x$, и тогда элемента $x$ нет в массиве $A$.

Скорость работы

Линейный поиск (последовательный просмотр всех элементов массива) выполняется за $O(N)$ операций, двоичный поиск - за $O(\log{N})$.

Пример реализации на C++

Шаблонная функция и пример её использования:
template <typename T> int binary_serch (const T *a,int n ,const T &elem);
Пусть $а$ - отсортированный массив, тогда функция за логарифмическое время возвращает $i$-ый индекс элемента массива elem=a[i] и -1, если элемент не найден.

#include <iostream> // Отсюда будем использовать вывод на экран при потоков (cout)
#include <algorithm> // Алгоритм сортировки (функция sort) из STL
#include <stdlib.h> // Функция rand() - случайные числа
#include <ctime> // Функция time() - время
#include <conio.h> // Функция getch() - ожидание нажатия клавиши в конце программы

// Шаблонная функция
template <typename T> int binary_search(const T *a, int n, const T &elem){
  int L = 0, R = n-1; // Левая и правая границы поиска
  while (L < R){ // Пока в рассматриваемом куске массива больше одного элемента
    int m = (L+R)/2; // Вычисляем индекс среднего элемента
    if (elem <= a[m]) // Если искомый элемент меньше центрального
      R = m; // Сдвигаем правую границу влево
    else // , а иначе
      L = m+1; // Левую границу вправо
  }
  // Остался один элемент с индеком L = R, 
  // и это либо искомый элемент elem, либо elem в массиве вообще нет!
  return (a[R] == elem) ? R : -1; // возвращаем индекс или -1 если элемент не найден 
}

using namespace std; // Чтобы не писать перед каждым cout "std::"

// Основная программа c примером использования
int main() {
  // Создаём случайный массив из N элементов
  const int N = 20;
  int a[N];
  // Заполняем массив a случайными целыми числами 
  srand(time(0)); // Инициализация генератора случайных чисел
  for(int i=0;i<N;i++)
    a[i] = rand() % 200; // случайные числа в диапазоне 0..199
  int el1 = a[rand() % N]; // Запоминаем случайный элемент массива
    // он точно будет в отсортированном массиве :)
  // Сортируем массив a при помощи функции sort из STL
  sort(a, a+N); // Да-да.. вот так просто, одной строкой, можно отсортировать массив ;)
  // Выводим массив на экран 
  for(int i=0;i<N;i++)
    cout << "a[" << i << "] = " << a[i] << endl;
  // Поиск элементов массива при помощи функции binary_search
  // Ищем элемент массива, который там заведомо есть 
  cout << "search " << el1 << " " << binary_search(a,N,el1) << endl;
  // Поиск элемента, которого в массиве a заведомо нет, т.к. он больше 199
  cout << "search " << 1000 << " " << binary_search(a,N,1000) << endl;

  cout << "Press any key..."; getch(); // Ожидаем нажатия клавиши :)
  return 0;
}

Стандартная STL функция binary_search возвращает лишь найден элемент или нет.

#include <iostream> // Вывод на экран
#include <algorithm> // Алгоритм сортировки из STL
#include <stdlib.h> // Функция rand() - случайные числа
#include <ctime> // Функция time() - время

// Основная программа для демонстрации функции 
using namespace std; // Чтобы не писать везде "std::"

int main() {
  // Создаём случайный массив из N элементов
  const int N = 20;
  int a[N];
  // Заполняем случайными числами 
  srand(time(0)); // Инициализация генератора случаных чисел
  for(int i=0;i<N;i++)
    a[i] = rand() % 200;
  int el1 = a[rand() % N]; // Запоминаем элемент массива
  // Сортируем массив a 
  sort(a, a+N);
  // Выводим массив на экран 
  for(int i=0;i<N;i++)
    cout << "a[" << i << "] = " << a[i] << endl;
  // Поиск элементов массива
  // Ищем элемент массива, который там заведомо есть 
  cout << "search " << el1 << " " << binary_search(a,a+N,el1) << endl;
  cout << "search " << 1000 << " " << binary_search(a,a+N,1000) << endl;
  return 0;
}

Реализация на Delphi

Добавить картинки

{$APPTYPE CONSOLE}

uses SysUtils;

procedure swap(var a, b: int64);
var t: int64;
begin
  t := a; a := b; b := t;
end;

var
  n, i, j, m, k, ans, l, r: integer;
  a: array [1..1000000] of int64;

procedure qsort(l, r: integer);
var
  i, j: integer;
  m: int64;
begin
  i := l;
  j := r;
  m := a[random(r - l + 1) + l];
  while i <= j do begin
    while a[i] < m do inc(i);
    while a[j] > m do dec(j);
    if i <= j then begin
      swap(a[i], a[j]);
      inc(i);
      dec(j);
    end;
  end;
  if i < r then qsort(i, r);
  if l < j then qsort(l, j);
end;

begin
  assign(input, 'find.in'); reset(input);
  assign(output, 'find.out'); rewrite(output);

  read(n, l);
  for i := 1 to n do
    read(a[i]);

  qsort(1, n);

  for j := 1 to l do begin
    read(k);
    l := 1;
    r := n + 1;
    While r - l > 1 do begin
      m := (r + l) div 2;
      if k >= a[m] then l := m else r := m;
    end;
    if k = a[l] then writeln('YES') else writeln('NO');
  end;
end.