Двоичный (бинарный) поиск, 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);
Пусть $a$ - отсортированный массив, тогда функция за логарифмическое время возвращает $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;
}
Реализация на Python
# Двоичный поиск в отсортированном списке: O(log n) по времени, O(1) по памяти
def binary_search(items, target):
"""Возвращает индекс элемента target в отсортированном списке или -1."""
left, right = 0, len(items) - 1
while left <= right:
middle = (left + right) // 2
if items[middle] == target:
return middle
if items[middle] < target:
left = middle + 1 # искомое значение правее середины
else:
right = middle - 1 # искомое значение левее середины
return -1
def main():
numbers = [1, 3, 5, 7, 9, 11, 13, 15]
for target in (7, 8, 1, 15):
print(f"search {target}: index {binary_search(numbers, target)}")
if __name__ == "__main__":
main()
Реализация на Rust
// Двоичный поиск в отсортированном срезе: O(log n) по времени, O(1) по памяти
pub fn binary_search(items: &[i64], target: i64) -> Option<usize> {
let mut left = 0;
let mut right = items.len();
while left < right {
let middle = left + (right - left) / 2;
match items[middle].cmp(&target) {
std::cmp::Ordering::Equal => return Some(middle),
std::cmp::Ordering::Less => left = middle + 1, // искомое значение правее середины
std::cmp::Ordering::Greater => right = middle, // искомое значение левее середины
}
}
None
}
fn main() {
let numbers = [1, 3, 5, 7, 9, 11, 13, 15];
for target in [7, 8, 1, 15] {
match binary_search(&numbers, target) {
Some(index) => println!("search {target}: index {index}"),
None => println!("search {target}: not found"),
}
}
}Интерактивно: двоичный поиск
Введите отсортированный массив и искомое число. На каждом шаге показан средний элемент и отрезок, в котором ещё может быть искомое.
Реализация на 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.