Merge pull request #1 from adambard/master

update

1 files changed, 64 insertions, 0 deletions

diff --git a/ru-ru/binary-search-ru.html.markdown b/ru-ru/binary-search-ru.html.markdown
new file mode 100644
index 00000000..9ed62cb8
--- /dev/null
+++ b/ru-ru/binary-search-ru.html.markdown
@@ -0,0 +1,64 @@
+---
+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/)