Двоичный поиск

Двоичный поиск
Двоичный поиск
	; Визуализация алгоритма, где 7 — целевое значение
Предназначение	Алгоритм поиска
Структура данных	Массив
Худшее время	O(log n)
Лучшее время	O(1)
Среднее время	O(log n)
Затраты памяти	O(log n)
	Медиафайлы на Викискладе

Двоичный (бинарный) поиск (также известен как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.

Визуализация бинарного поиска по массиву. Искомое число — 7.

Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.

Поиск элемента в отсортированном массивеПравить

Имеется викиучебник по теме «Реализации алгоритмов/Двоичный поиск»

Определение значения элемента в середине структуры данных. Полученное значение сравнивается с ключом.
Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.

Несмотря на то, что код достаточно прост, в нём есть несколько ловушек.

Код (first + last) / 2 ошибочен, если first и last по отдельности умещаются в свой тип, а first+last — нет^[1]. Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
- Использовать код first + (last - first) / 2, который точно не приведёт к переполнениям, если имеем дело с неотрицательными целыми числами и first<last.
  - Если first и last — указатели или итераторы, такой код единственно правильный, поскольку не нарушает абстракцию (уже операция «указатель + указатель» некорректна). Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «указатель+число → указатель», «указатель−указатель → число».
- Если first и last — типы со знаком, провести расчёт в беззнаковом типе: ((unsigned)first + (unsigned)last) / 2. В Java сработает такой код: (first + last) >>> 1 (знаковое двоичное сложение совпадает с беззнаковым, Java гарантирует такое поведение даже при переполнении, и вся эта формула оперирует знаковыми числами как беззнаковыми).
- Написать расчёт на ассемблере, с использованием флага переноса. Что-то наподобие add eax, b; rcr eax, 1. А вот длинные типы использовать нецелесообразно, first + (last - first) / 2 быстрее.
В двоичном поиске часты ошибки на единицу, и каждая такая ошибка превращается в зацикливание, пропуск или выход за пределы массива. Поэтому важно протестировать такие случаи: пустой массив (n=0), один элемент (n=1), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент.
Иногда требуется, чтобы, если x в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не x, а следующий за ним элемент).^[2] Например, функция std::lower_bound из C++ находит первый из равных, а std::upper_bound — элемент, следующий за x. Если не найдено — оба возвращают место, куда вставить.

Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям^[1].

Пример реализации на JavaПравить

int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = arr[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

Пример реализации на C#Править

public static int BinarySearch(long[] arr, long key)
{
    int left = 0;
    int right = arr.Length - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key)
        {
            return mid;
        }
        else if (arr[mid] < key)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return -1;
}

ПриложенияПравить

Практические приложения метода двоичного поиска разнообразны:

Широкое распространение в информатике применительно к поиску в структурах данных. Например, поиск в массивах данных осуществляется по ключу, присвоенному каждому из элементов массива (в простейшем случае сам элемент является ключом).
Также его применяют в качестве численного метода для нахождения приближённого решения уравнений (см. Метод бисекции).
Метод используется для нахождения экстремума целевой функции и в этом случае является методом условной одномерной оптимизации. Когда функция имеет вещественный аргумент, найти решение с точностью до $\text{[math]}$ $\text{[math]}$ $\varepsilon$ можно за время $\text{[math]}$ $\text{[math]}$ $\log _{2}1/\varepsilon$ . Когда аргумент дискретен, и изначально лежит на отрезке длины N, поиск решения займёт $\text{[math]}$ $\text{[math]}$ $1+\log _{2}N$ времени. Наконец, для поиска экстремума, скажем, для определённости минимума, на очередном шаге отбрасывается тот из концов рассматриваемого отрезка, значение в котором максимально.

См. такжеПравить

ПримечанияПравить

↑ ¹ ² Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken Архивная копия от 2 декабря 2013 на Wayback Machine // Joshua Bloch, Google Research; перевод — Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка Архивная копия от 24 ноября 2013 на Wayback Machine
↑ В C++ std::lower_bound находит первое вхождение x, а std::upper_bound — элемент, следующий за x.

ЛитератураПравить

Левитин А. В. Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 180—183. — 576 с. — ISBN 978-5-8459-0987-9
Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
Вирт Н. Алгоритмы + структуры данных = программы. — М.: «Мир», 1985. — С. 28.
Волков Е. А. Численные методы. — М.: Физматлит, 2003.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4.

СсылкиПравить

[joshua-1] ¹ ² Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken Архивная копия от 2 декабря 2013 на Wayback Machine // Joshua Bloch, Google Research; перевод — Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка Архивная копия от 24 ноября 2013 на Wayback Machine

[2] В C++ std::lower_bound находит первое вхождение x, а std::upper_bound — элемент, следующий за x.

[1]

[2]

Двоичный поиск
Визуализация алгоритма, где 7 — целевое значение
Предназначение	Алгоритм поиска
Структура данных	Массив
Худшее время	O(log n)
Лучшее время	O(1)
Среднее время	O(log n)
Затраты памяти	O(log n)
Медиафайлы на Викискладе