Алгоритм двоичного поиска c

Алгоритм двоичного поиска c

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

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

Содержание

Поиск элемента в отсортированном массиве [ править | править код ]

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

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

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

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

    Приложения [ править | править код ]

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

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

    Сегодня мы и изучим его. Также попытаемся ответить на такие вопросы: как бинарный поиск работает в программе, плюсы и минусы его использования у себя в коде и в каких структурах данных можно его применять, а в каких нет. Поехали!

    Что такое бинарный поиск

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

    Очень важно помнить! Алгоритм будет работать правильно, только с отсортированным массивом. А если по случайности вы забыли отсортировать массив перед его использованием, то в большинстве случаев тот ответ, который подсчитал алгоритм, будет неверным.

    Читайте также:  Смартфон уроки для чайников

    Принцип работы бинарного поиска

    Давайте рассмотрим задачку, чтобы понять как работает алгоритм.
    Охранной службе морского флота поступило сообщение о том, что некто пытается пронести на корабль бомбу. Диверсант пока находится у причала. Допустим, что в нашем распоряжении имеется прибор, который может определить, есть ли бомба в комнате. Необходимо как можно быстрее определить, у кого находится бомба.

    Самым легким и самым долгим по времени решением, будет поочередная проверка пассажиров в комнате с прибором (это линейный поиск). Но это слишком долго.

    Давайте сделаем по-другому. Поделим пополам всех пассажиров и разведем их по двум комнатам. Так с помощью прибора мы сможем узнать, в какой из двух комнат находится бомба. В итоге такого маневра мы уменьшим число подозреваемых в два раза. С остальным числом подозреваемых сделаем также: разделим их на две группы и разместим в разных комнатах. Так продолжаем, пока не узнаем кто диверсант.

    В задаче выше охранники использовали алгоритм двоичного поиска для нахождения диверсанта. В обычной программе принцип работы бинарного поиска такой же, как и в примере, выше.

    Как создать бинарный поиск в C++

    Давайте посмотрим как работает бинарный поиск на примере.В примере ниже в строке 9 мы создали массив arr на 10 элементов и в строке 12 предложили пользователю с клавиатуры заполнить его ячейки.

    В строке 20 мы предлагаем пользователю ввести ключ (который нужно будет найти в массиве), а дальше мы с бинарным поиском проверим массив на наличие введенного ключа пользователем. Если мы найдем ключ в массиве, то выведем индекс ячейки, в которой находится ключ.

    Бинарный поиск производится в упорядоченном массиве.

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

    Читайте также:  Как найти площадь окружности вписанной в треугольник

    Алгоритм может быть определен в рекурсивной и нерекурсивной формах.

    Бинарный поиск также называют поиском методом деления отрезка пополам или дихотомии .

    Количество шагов поиска определится как

    где n-количество элементов,
    — округление в большую сторону до ближайшего целого числа.

    На каждом шаге осуществляется поиск середины отрезка по формуле

    Если искомый элемент равен элементу с индексом mid, поиск завершается.
    В случае если искомый элемент меньше элемента с индексом mid, на место mid перемещается правая граница рассматриваемого отрезка, в противном случае — левая граница.

      Подготовка . Перед началом поиска устанавливаем левую и правую границы массива:

    left = 0, right = 19

    Шаг 1 . Ищем индекс середины массива (округляем в меньшую сторону):

    Сравниваем значение по этому индексу с искомым:

    69
    Шаг 2 . Ищем индекс середины массива (округляем в меньшую сторону):

    Сравниваем значение по этому индексу с искомым:

    84 > 82

    Сдвигаем правую границу:

    right = m >
    Шаг 3 . Ищем индекс середины массива (округляем в меньшую сторону):

    Сравниваем значение по этому индексу с искомым:

    78
    Шаг 4 . Ищем индекс середины массива (округляем в меньшую сторону):

    Сравниваем значение по этому индексу с искомым:

    80
    Шаг 5 . Ищем индекс середины массива (округляем в меньшую сторону):

    Сравниваем значение по этому индексу с искомым:

    82 = 82

    Решение найдено!

    Чтобы уменьшить количество шагов поиска можно сразу смещать границы поиска на элемент, следующий за серединой отрезка:

    left = mid + 1
    right = mid — 1

    Ссылка на основную публикацию
    Adblock detector