Различия

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

--- basics_of_algorithms:binary_search [2023/10/03 18:45]
werwolf [Как реализовать бинарный поиск]
+++ basics_of_algorithms:binary_search [2023/10/03 19:43] (текущий)
werwolf [Как реализовать бинарный поиск]
@@ Строка 1: / Строка 1: @@
 ====== Бинарный поиск — Основы алгоритмов и структур данных ======
 Мы постоянно что-то ищем с помощью компьютера: номера телефона, свободные номера в гостиницах, товары в интернет-магазинах, квартиры в аренду. Даже сайты мы ищем с помощью поисковой машины. За каждым из этих поисков скрываются разные алгоритмы. Среди них — поиск подстроки, поиск по ключевым словам, префиксный поиск.
@@ Строка 98: / Строка 97: @@
 </code>
-Python
+<details>
+<summary>Python</summary>
 <code python>
 stop_words = ['ее', 'на', 'по', 'со', 'же', 'браво', 'всего', 'я', 'итого']
@@ Строка 109: / Строка 108: @@
     return False
 </code>
+</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>
 ==== Недостатки бинарного поиска ====
@@ Строка 720: / Строка 771: @@
 И третье ограничение — некоторые данные просто нельзя упорядочить. Например, не существует какого-то естественного общепризнанного способа упорядочить цвета:
-{{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjNlY2RiNmFmZTNiZjU5NGJhYTE3YWQwNTI4ODJhZTJhLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=79405509d9f406a665a6eeb6edffe0ff249c44e89dcc7b9a3f1c7e00ec3a91cc|Цвета}}Таким же образом, сложно упорядочить пары чисел. Возьмем для примера широту и долготу — это как раз пара чисел:
+{{ :basics_of_algorithms:image_processing20231003-35-vql2f3.png |}}
+Таким же образом, сложно упорядочить пары чисел. Возьмем для примера широту и долготу — это как раз пара чисел:
   * Самый западный город России — Балтийск, его координаты 54°39′ с. ш. 19°55′ в. д.
@@ Строка 766: / Строка 819: @@
   * У метода перебора есть два варианта: Простой перебор, чтобы проверить, есть ли элемент в списке
-===== Для полного доступа к курсу нужен базовый план =====
-Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
-[[:subscription:new?nickname=professional_monthly_3900|Получить доступ]]
-----
-[[:courses|курсов]]
-упражнений
-+
-часов теории
-тестов

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

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

Различия

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