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

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

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

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

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

• Код (first + last) / 2 ошибочен, если first и last по отдельности умещаются в свой тип, а first+last — нет . Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
  • Использовать код 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 , а следующий за ним элемент). Например, функция std :: lower_bound из C++ находит первый из равных, а std :: upper_bound — элемент, следующий за x. Если не найдено — оба возвращают место, куда вставить.

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

Пример реализации на 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)
{
    if(arr.Length==0)
    {
     throw new Exception("Array without elements for search");
    }
    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;
}

Пример реализации на Python

def binary_search(list, key):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        midVal = list[mid]
        if midVal == key:
            return mid
        if midVal > key:
            high = mid - 1
        else:
            low = mid + 1
    return 'not found :('

Пример реализации на Javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const binarySearch = (nums, target) => {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        const midIndex = (left + right) >> 1;
        const mid = nums[midIndex];
        if (mid === target) {
            return midIndex;
        } else if (mid > target) {
            right = midIndex - 1;
        } else {
            left = midIndex + 1;
        }
    }
    return -1; 
};

Приложения

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

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

См. также

• Линейный поиск
• Метод бисекции
• Метод дихотомии
• Метод Ньютона
• Метод золотого сечения
• Троичный поиск

Примечания

Литература

• Глава 4. Метод декомпозиции: Бинарный поиск // — М. : , 2006. — С. 180—183. — 576 с. — ISBN 978-5-8459-0987-9
• Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М. : Мир, 1998.
• Бахвалов Н. С., Жидков Н. П. , Кобельков Г. Г. Численные методы. — 8-е изд. — М. : Лаборатория Базовых Знаний, 2000.
• Вирт Н. . — М. : « Мир », 1985. — С. .
• Волков Е. А. Численные методы. — М. : Физматлит, 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 .

Ссылки