Add binary search algorithm documentation and code

qqracha · qqracha · commit 4d578e9732e1 · 2025-08-21T23:30:30.000+02:00
Added binarySearch.md with explanation and code sample, binarySearch.py with the implementation, and a related diagram binarySearch.png. Also added ruber.xml to project dictionaries.
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1 @@
+.idea/dictionaries/ruber.xml
diff --git a/source/binarySearch.png b/source/binarySearch.png
diff --git a/templates/binarySearch.md b/templates/binarySearch.md
@@ -0,0 +1,31 @@
+
+## Binary Search (Бинарный поиск)
+**Идея:** Делим отсортированный массив пополам и каждый раз отбрасываем ненужную половину.
+
+![Binary Search](../source/binarySearch.png)
+- **Когда использовать:**
+  - Когда массив/список **отсортирован**.
+  - Нужно быстро найти элемент или проверить его наличие.
+  - Примеры: поиск слова в словаре, поиск числа в отсортированном списке, задачи типа *«найди минимальное значение X, которое удовлетворяет условию»*.
+
+- **Сложность:**
+  - Время: **O(log n)**
+  - Память: **O(1)** (итеративно) или **O(log n)** (рекурсивно).
+
+- **Проблемы, которые решает:**
+  - Поиск позиции элемента в массиве.
+  - Оптимизационные задачи на *монотонные функции*.
+
+## Код
+```python
+def binary_search(arr, target):
+    left, right = 0, len(arr) - 1
+    while left <= right:
+        mid = (left + right) // 2
+        if arr[mid] == target:
+            return mid
+        elif arr[mid] < target:
+            left = mid + 1
+        else:
+            right = mid - 1
+    return -1
diff --git a/templates/binarySearch.py b/templates/binarySearch.py
@@ -0,0 +1,14 @@
+# Binary Search (бинарный поиск)
+def binary_search(arr, target):
+    left, right = 0, len(arr) - 1
+    while left <= right:
+        mid = (left + right) // 2
+        if arr[mid] == target:
+            return mid
+        elif arr[mid] < target:
+            left = mid + 1
+        else:
+            right = mid - 1
+    return -1
+
+
