Различия

Здесь показаны различия между двумя версиями данной страницы.

--- basics_of_algorithms:binary_search [2023/10/03 18:54]
werwolf [Как ускорить алгоритм перебора]
+++ basics_of_algorithms:binary_search [2023/10/03 19:43] (текущий)
werwolf [Как реализовать бинарный поиск]
@@ Строка 1: / Строка 1: @@
 ====== Бинарный поиск — Основы алгоритмов и структур данных ======
 Мы постоянно что-то ищем с помощью компьютера: номера телефона, свободные номера в гостиницах, товары в интернет-магазинах, квартиры в аренду. Даже сайты мы ищем с помощью поисковой машины. За каждым из этих поисков скрываются разные алгоритмы. Среди них — поиск подстроки, поиск по ключевым словам, префиксный поиск.
@@ Строка 98: / Строка 97: @@
 </code>
-Python
+<details>
-~~stoggle_openDIV~~
+<summary>Python</summary>
 <code python>
 stop_words = ['ее', 'на', 'по', 'со', 'же', 'браво', 'всего', 'я', 'итого']
@@ Строка 109: / Строка 108: @@
     return False
 </code>
- ~~stoggle_closeDIV~~
+</details>
-PHP
+<details>
+<summary>PHP</summary>
 <code php>
 <?php
@@ Строка 128: / Строка 130: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
-<code php>
+<code java>
 class App {
@@ Строка 149: / Строка 152: @@
 }
 </code>
+</details>
 Функция ''isStopWord()'' перебирает **слова-кандидаты**, последовательно сравнивает их с каждой строкой в массиве стоп-слов и возвращает ''true'' или ''false''. Мы вставили сюда слова из нашей таблицы, но, чтобы код не получился слишком большим, ограничились десятком слов.
@@ Строка 235: / Строка 239: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
 stop_words = ['а', 'без', 'ближе', 'браво', 'бы', 'вам', 'вас', 'весь', 'во', 'все', 'всего', 'вы']
@@ Строка 263: / Строка 268: @@
     return False
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
 <code php>
 <?php
@@ Строка 293: / Строка 299: @@
 };
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
 <code java>
 class App {
@@ Строка 332: / Строка 339: @@
 }
 </code>
+</details>
-https://replit.com/@hexlet/algorithms-binary-search
-https://replit.com/@hexlet/binarysearch
 Разберемся, как эта функция работает. На каждом шаге алгоритма мы взаимодействуем с областью поиска. Чтобы определить ее, нам достаточно хранить индексы его первого и последнего элементов. В самом начале область поиска совпадает со всем массивом.
@@ Строка 346: / Строка 351: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
 # индекс первого элемента области поиска
@@ Строка 354: / Строка 360: @@
 last = len(stop_words) - 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
 <code php>
 <?php
@@ Строка 363: / Строка 370: @@
 $last = count(stopWords) - 1;
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
 <code java>
 // индекс первого элемента области поиска
@@ Строка 372: / Строка 381: @@
 var last = stopWords.size() - 1;
 </code>
+</details>
 Элементы в массивах JavaScript нумеруются с нуля, поэтому сначала индекс первого элемента равен 0, а индекс последнего — на единицу меньше длины массива. Чтобы убедиться в этом, представьте массив, например, из четырех элементов: его элементы будут иметь индексы 0, 1, 2 и 3.
@@ Строка 381: / Строка 391: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
 middle = (first + last) / 2
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
 <code php>
 <?php
@@ Строка 394: / Строка 406: @@
 $middle = ($first + $last) / 2
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
 <code java>
 var middle = (first + last) / 2;
 </code>
+</details>
 В массиве с нечетным количеством элементов все просто: у нас есть центральный элемент и две равные половины слева и справа от него. В массиве с четным количеством элементов, длина левой и правой половин будет отличаться на единицу.
@@ Строка 412: / Строка 426: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
 middle = (first + last) // 2
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
 <code php>
 $middle = round(($first + $last) / 2);
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
 <code java>
 // В Java для целых чисел используется целочисленное деление
 var middle = (first + last) / 2;
 </code>
+</details>
 Дальше есть три варианта развития событий.
@@ Строка 441: / Строка 458: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
 last = middle
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
 <code php>
 <?php
@@ Строка 454: / Строка 472: @@
 $last = $middle;
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
 <code java>
 last = middle;
 </code>
+<details>
 На самом деле мы можем не включать центральное слово в новую область. При проверке первого варианта мы убедились, что слово-кандидат с ним не совпадает. Новым последним словом будет то, которое находится слева от центрального:
 <code javascript>
@@ Строка 467: / Строка 487: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
 last = middle - 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
 <code php>
 <?php
@@ Строка 480: / Строка 501: @@
 $last = $middle - 1;
 </code>
+<details>
-Java
+<details>
+<summary>Java</summary>
 <code java>
 last = middle - 1;
 </code>
+</details>
 **Вариант 3:** Слово-кандидат может быть больше центрального слова. Тогда вместо правой границы надо двигать левую. Код окажется очень похожим:
@@ Строка 493: / Строка 516: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
 first = middle + 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
-<code php>
+<code>
 <?php
 $first = $middle + 1;
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
 <code java>
 first = middle + 1;
 </code>
+</details>
 Мы сократили область поиска вдвое, а теперь надо повторить предыдущие шаги — тогда в нашей программе появится цикл:
@@ Строка 535: / Строка 562: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
 while (???):
@@ Строка 553: / Строка 581: @@
         first = middle + 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
 <code php>
 <?php
@@ Строка 577: / Строка 606: @@
 }
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
 <code java>
@@ Строка 599: / Строка 630: @@
     }
 </code>
+</details>
 Мы пока не знаем условия завершения цикла, поэтому написали три знака вопроса. Чтобы разобраться с условием, обратим внимание, что на каждом шаге первое и последнее слово двигаются к друг другу и когда-нибудь они совпадут. Тогда условие ''first === last'' станет истинным.
@@ Строка 611: / Строка 643: @@
 Слово-кандидат либо будет совпадать с центральным словом, либо нет. Если оно окажется меньше, у нас выполнится ветка:
-<code javascript>
+<code javasript>
 last = middle - 1;
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
 last = middle - 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
 <code php>
@@ Строка 628: / Строка 662: @@
 $last = $middle - 1;
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
 <code java>
 last = middle - 1;
 </code>
+</details>
 Мы помним, что значения ''first'', ''last'' и ''middle'' совпадают, так что новое значение ''last'' окажется на единицу меньше ''first''. Ситуация кажется странной — как последнее слово может находиться перед первым?
@@ Строка 645: / Строка 682: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
 first = middle + 1
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
 <code php>
@@ Строка 658: / Строка 699: @@
 $first = $middle + 1;
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
 <code java>
 first = middle + 1;
 </code>
+</details>
 Цикл следует остановить, когда левая граница станет больше правой. Но в операторе ''while'' мы записываем не условие остановки цикла, а условие продолжения, поэтому условие надо поменять на обратное: ''first <= last''. Если цикл завершается и кандидат в списке не найден, значит, поиск завершился неудачно — алгоритм вернет ''false'':
 <code javascript>
 // пока область поиска не пуста
 while (first <= last) {
@@ Строка 676: / Строка 720: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
@@ Строка 685: / Строка 731: @@
 return False
 </code>
+</details>
-PHP
+<details>
+<summary>PHP</summary>
 <code php>
@@ Строка 698: / Строка 746: @@
 return false;
 </code>
+</details>
-Java
+<details>
+<summary>Java</summary>
 <code java>
@@ Строка 707: / Строка 757: @@
 }
 </code>
+</details>
 ==== Недостатки бинарного поиска ====

Инструменты пользователя

Инструменты сайта

Различия

Инструменты страницы