diff options
Diffstat (limited to 'ru-ru/binary-search-ru.html.markdown')
| -rw-r--r-- | ru-ru/binary-search-ru.html.markdown | 62 |
1 files changed, 0 insertions, 62 deletions
diff --git a/ru-ru/binary-search-ru.html.markdown b/ru-ru/binary-search-ru.html.markdown deleted file mode 100644 index c2d3767a..00000000 --- a/ru-ru/binary-search-ru.html.markdown +++ /dev/null @@ -1,62 +0,0 @@ ---- -category: Algorithms & Data Structures -name: Binary Search -contributors: - - ["Abhishek Jaisingh", "http://github.com/abhishekjiitr"] -translators: - - ["Evan K.", "https://github.com/justblah"] -lang: ru-ru ---- - -# Двоичный (бинарный) поиск - -## Зачем использовать двоичный поиск? - -Поиск является одной из главных проблем в области вычислительной техники. На сегодняшний день осуществляется более одного триллиона поисковых запросов в год, поэтому нам нужны алгоритмы, которые могут делать это очень быстро. Двоичный поиск является одним из фундаментальных алгоритмов в информатике. Для его изучения мы освоим теорию, а затем используем её для реализации алгоритма. - -## Вступление - -Самый простой вариант поиска – линейный поиск, но этот подход занимает много времени, и растет линейно, пропорционально набору данных. Пример реализации – начинаем с крайнего левого элемента массива S, один за другим сравниваем искомое значение X с каждым элементом массива S, если X совпадает с элементом S, возвращаем индекс. Если X не совпадает ни с одним из элементов массива S, возвращаем -1. - -``` -Линейный поиск: O (n) Линейная сложность - -Двоичный поиск: O ( log(n) ) Логарифмическая сложность -``` - -``` -def search(arr, x): - - for i in range(len(arr)): - - if arr[i] == x: - return i - - return -1 -``` - -## Алгоритм двоичного поиска - -Для корректной работы двоичного поиска набор данных для поиска должен быть отсортирован (в любом порядке). - -### Алгоритм - -``` -Главная идея двоичного поиска заключается в использовании информации о том, что массив уже отсортирован, -что и позволяет упростить сложность алгоритма до O(Logn). Мы попросту отбрасываем половину элементов набора сразу после одного сравнения. -1) Сравнить X с элементом в середине набора S. -2) Если X равен элементу в середине - возвращаем индекс среднего элемента. -3) Если значение X больше, чем средний элемент набора, значит X находится в правой части набора. Повторяем алгоритм для правой половины набора. -4) В противном случае (X меньше) повторяем алгоритм для левой половины набора. -Это и есть рекурсивная реализация двоичного поиска. -``` - -### На заметку - -Существует и другая форма двоичного поиска, которая может быть полезна. - -## На почитать - -* [Проектирование, реализация и примеры](https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA) -* [Описание алгоритма ИТМО](http://neerc.ifmo.ru/wiki/index.php?title=%D0%A6%D0%B5%D0%BB%D0%BE%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA) -* [Ошибки при реализации бинарного поиска](https://habrahabr.ru/post/146228/) |