Инструменты пользователя
basics_of_algorithms:binary_search
Различия
Здесь показаны различия между двумя версиями данной страницы.
| Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия | ||
|
basics_of_algorithms:binary_search [2023/10/03 19:22] werwolf [Как ускорить алгоритм перебора] |
basics_of_algorithms:binary_search [2023/10/03 19:43] (текущий) werwolf [Как реализовать бинарный поиск] |
||
|---|---|---|---|
| Строка 114: | Строка 114: | ||
| <details> | <details> | ||
| <summary>PHP</summary> | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 134: | Строка 134: | ||
| <details> | <details> | ||
| <summary>Java</summary> | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| Строка 207: | Строка 207: | ||
| Вот функция, которая проверяет, есть ли стоп-слово в отсортированном массиве: | Вот функция, которая проверяет, есть ли стоп-слово в отсортированном массиве: | ||
| - | <code> | + | <code javascript> |
| const stopWords = ['а', 'без', 'ближе', 'браво', 'бы', 'вам', 'вас', 'весь', 'во', 'все', 'всего', 'вы']; | const stopWords = ['а', 'без', 'ближе', 'браво', 'бы', 'вам', 'вас', 'весь', 'во', 'все', 'всего', 'вы']; | ||
| Строка 239: | Строка 239: | ||
| </code> | </code> | ||
| - | Python | ||
| - | <code> | + | <details> |
| + | <summary>Python</summary> | ||
| + | <code python> | ||
| stop_words = ['а', 'без', 'ближе', 'браво', 'бы', 'вам', 'вас', 'весь', 'во', 'все', 'всего', 'вы'] | stop_words = ['а', 'без', 'ближе', 'браво', 'бы', 'вам', 'вас', 'весь', 'во', 'все', 'всего', 'вы'] | ||
| Строка 267: | Строка 268: | ||
| return False | return False | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| - | + | <summary>PHP</summary> | |
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 297: | Строка 299: | ||
| }; | }; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| - | + | <summary>Java</summary> | |
| - | <code> | + | <code java> |
| class App { | class App { | ||
| Строка 336: | Строка 339: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | https://replit.com/@hexlet/algorithms-binary-search | ||
| - | |||
| - | https://replit.com/@hexlet/binarysearch | ||
| Разберемся, как эта функция работает. На каждом шаге алгоритма мы взаимодействуем с областью поиска. Чтобы определить ее, нам достаточно хранить индексы его первого и последнего элементов. В самом начале область поиска совпадает со всем массивом. | Разберемся, как эта функция работает. На каждом шаге алгоритма мы взаимодействуем с областью поиска. Чтобы определить ее, нам достаточно хранить индексы его первого и последнего элементов. В самом начале область поиска совпадает со всем массивом. | ||
| - | <code> | + | <code javascript> |
| // индекс первого элемента области поиска | // индекс первого элемента области поиска | ||
| let first = 0; | let first = 0; | ||
| Строка 350: | Строка 351: | ||
| </code> | </code> | ||
| - | Python | ||
| - | <code> | + | <details> |
| + | <summary>Python</summary> | ||
| + | <code python> | ||
| # индекс первого элемента области поиска | # индекс первого элемента области поиска | ||
| first = 0 | first = 0 | ||
| Строка 358: | Строка 360: | ||
| last = len(stop_words) - 1 | last = len(stop_words) - 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| - | + | <summary>PHP</summary> | |
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 367: | Строка 370: | ||
| $last = count(stopWords) - 1; | $last = count(stopWords) - 1; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | ||
| - | <code> | + | <details> |
| + | <summary>Java</summary> | ||
| + | <code java> | ||
| // индекс первого элемента области поиска | // индекс первого элемента области поиска | ||
| var first = 0; | var first = 0; | ||
| Строка 376: | Строка 381: | ||
| var last = stopWords.size() - 1; | var last = stopWords.size() - 1; | ||
| </code> | </code> | ||
| + | </details> | ||
| Элементы в массивах JavaScript нумеруются с нуля, поэтому сначала индекс первого элемента равен 0, а индекс последнего — на единицу меньше длины массива. Чтобы убедиться в этом, представьте массив, например, из четырех элементов: его элементы будут иметь индексы 0, 1, 2 и 3. | Элементы в массивах JavaScript нумеруются с нуля, поэтому сначала индекс первого элемента равен 0, а индекс последнего — на единицу меньше длины массива. Чтобы убедиться в этом, представьте массив, например, из четырех элементов: его элементы будут иметь индексы 0, 1, 2 и 3. | ||
| Строка 381: | Строка 387: | ||
| На каждом шаге мы сравниваем слово-кандидат со словом из середины области. Найти среднее слово несложно: его индекс находится посередине между первым и последним словом. | На каждом шаге мы сравниваем слово-кандидат со словом из середины области. Найти среднее слово несложно: его индекс находится посередине между первым и последним словом. | ||
| - | <code> | + | <code javascript> |
| const middle = (first + last) / 2; | const middle = (first + last) / 2; | ||
| </code> | </code> | ||
| - | Python | ||
| - | <code> | + | <details> |
| + | <summary>Python</summary> | ||
| + | <code python> | ||
| middle = (first + last) / 2 | middle = (first + last) / 2 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| - | + | <summary>PHP</summary> | |
| - | <code> | + | <code php> |
| <?php | <?php | ||
| $middle = ($first + $last) / 2 | $middle = ($first + $last) / 2 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| - | + | <summary>Java</summary> | |
| - | <code> | + | <code java> |
| var middle = (first + last) / 2; | var middle = (first + last) / 2; | ||
| </code> | </code> | ||
| + | </details> | ||
| В массиве с нечетным количеством элементов все просто: у нас есть центральный элемент и две равные половины слева и справа от него. В массиве с четным количеством элементов, длина левой и правой половин будет отличаться на единицу. | В массиве с нечетным количеством элементов все просто: у нас есть центральный элемент и две равные половины слева и справа от него. В массиве с четным количеством элементов, длина левой и правой половин будет отличаться на единицу. | ||
| Строка 411: | Строка 421: | ||
| Чтобы справиться с этой ситуацией, мы округлим это значение вверх или вниз. Если вниз — левая половина будет на один элемент короче правой, а если вверх — наоборот. Можно выбрать любой вариант, алгоритм будет работать в обоих случаях. Округлим значение в меньшую сторону: | Чтобы справиться с этой ситуацией, мы округлим это значение вверх или вниз. Если вниз — левая половина будет на один элемент короче правой, а если вверх — наоборот. Можно выбрать любой вариант, алгоритм будет работать в обоих случаях. Округлим значение в меньшую сторону: | ||
| - | <code> | + | <code javascript> |
| // индекс среднего элемента области поиска | // индекс среднего элемента области поиска | ||
| const middle = Math.floor((first + last) / 2); | const middle = Math.floor((first + last) / 2); | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| - | + | <summary>Python</summary> | |
| - | <code> | + | <code python> |
| middle = (first + last) // 2 | middle = (first + last) // 2 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| - | + | <summary>PHP</summary> | |
| - | <code> | + | <code php> |
| $middle = round(($first + $last) / 2); | $middle = round(($first + $last) / 2); | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| - | + | <summary>Java</summary> | |
| - | <code> | + | <code java> |
| // В Java для целых чисел используется целочисленное деление | // В Java для целых чисел используется целочисленное деление | ||
| var middle = (first + last) / 2; | var middle = (first + last) / 2; | ||
| </code> | </code> | ||
| + | </details> | ||
| Дальше есть три варианта развития событий. | Дальше есть три варианта развития событий. | ||
| Строка 441: | Строка 454: | ||
| **Вариант 2:** Слово-кандидат может быть меньше слова из середины. Тогда надо отбросить все элементы справа и продолжать поиск только в левой части. На следующем шаге первое слово останется прежним, а последнее изменится. Последним словом в новой области поиска станет центральное слово из старой: | **Вариант 2:** Слово-кандидат может быть меньше слова из середины. Тогда надо отбросить все элементы справа и продолжать поиск только в левой части. На следующем шаге первое слово останется прежним, а последнее изменится. Последним словом в новой области поиска станет центральное слово из старой: | ||
| - | <code> | + | <code javascript> |
| last = middle; | last = middle; | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| - | + | <summary>Python</summary> | |
| - | <code> | + | <code python> |
| last = middle | last = middle | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| - | + | <summary>PHP</summary> | |
| - | <code> | + | <code php> |
| <?php | <?php | ||
| $last = $middle; | $last = $middle; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| - | + | <summary>Java</summary> | |
| - | <code> | + | <code java> |
| last = middle; | last = middle; | ||
| </code> | </code> | ||
| + | <details> | ||
| - | На самом деле мы можем не включать центральное слово в новую область. При проверке первого варианта мы убедились, что слово-кандидат с ним не совпадает. Новым последним словом будет то, которое находится слева от центрального: | + | На самом деле мы можем не включать центральное слово в новую область. При проверке первого варианта мы убедились, что слово-кандидат с ним не совпадает. Новым последним словом будет то, которое находится слева от центрального: |
| - | <code> | + | <code javascript> |
| last = middle - 1; | last = middle - 1; | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| - | + | <summary>Python</summary> | |
| - | <code> | + | <code python> |
| last = middle - 1 | last = middle - 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| - | + | <summary>PHP</summary> | |
| - | <code> | + | <code php> |
| <?php | <?php | ||
| $last = $middle - 1; | $last = $middle - 1; | ||
| </code> | </code> | ||
| + | <details> | ||
| - | Java | + | <details> |
| - | + | <summary>Java</summary> | |
| - | <code> | + | <code java> |
| last = middle - 1; | last = middle - 1; | ||
| </code> | </code> | ||
| + | </details> | ||
| **Вариант 3:** Слово-кандидат может быть больше центрального слова. Тогда вместо правой границы надо двигать левую. Код окажется очень похожим: | **Вариант 3:** Слово-кандидат может быть больше центрального слова. Тогда вместо правой границы надо двигать левую. Код окажется очень похожим: | ||
| - | <code> | + | <code javascript> |
| first = middle + 1; | first = middle + 1; | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| first = middle + 1 | first = middle + 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| <code> | <code> | ||
| <?php | <?php | ||
| Строка 510: | Строка 531: | ||
| $first = $middle + 1; | $first = $middle + 1; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| - | + | <summary>Java</summary> | |
| - | <code> | + | <code java> |
| first = middle + 1; | first = middle + 1; | ||
| </code> | </code> | ||
| + | </details> | ||
| Мы сократили область поиска вдвое, а теперь надо повторить предыдущие шаги — тогда в нашей программе появится цикл: | Мы сократили область поиска вдвое, а теперь надо повторить предыдущие шаги — тогда в нашей программе появится цикл: | ||
| - | <code> | + | <code javascript> |
| while (???) { | while (???) { | ||
| // индекс среднего элемента области поиска | // индекс среднего элемента области поиска | ||
| Строка 539: | Строка 562: | ||
| </code> | </code> | ||
| - | Python | ||
| - | <code> | + | <details> |
| + | <summary>Python</summary> | ||
| + | <code python> | ||
| while (???): | while (???): | ||
| # индекс среднего элемента области поиска | # индекс среднего элемента области поиска | ||
| Строка 557: | Строка 581: | ||
| first = middle + 1 | first = middle + 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| - | + | <summary>PHP</summary> | |
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 581: | Строка 606: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| while (???) { | while (???) { | ||
| // индекс среднего элемента области поиска | // индекс среднего элемента области поиска | ||
| Строка 603: | Строка 630: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Мы пока не знаем условия завершения цикла, поэтому написали три знака вопроса. Чтобы разобраться с условием, обратим внимание, что на каждом шаге первое и последнее слово двигаются к друг другу и когда-нибудь они совпадут. Тогда условие ''first === last'' станет истинным. | Мы пока не знаем условия завершения цикла, поэтому написали три знака вопроса. Чтобы разобраться с условием, обратим внимание, что на каждом шаге первое и последнее слово двигаются к друг другу и когда-нибудь они совпадут. Тогда условие ''first === last'' станет истинным. | ||
| Строка 615: | Строка 643: | ||
| Слово-кандидат либо будет совпадать с центральным словом, либо нет. Если оно окажется меньше, у нас выполнится ветка: | Слово-кандидат либо будет совпадать с центральным словом, либо нет. Если оно окажется меньше, у нас выполнится ветка: | ||
| - | <code> | + | <code javasript> |
| last = middle - 1; | last = middle - 1; | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| - | + | <summary>Python</summary> | |
| - | <code> | + | <code python> |
| last = middle - 1 | last = middle - 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| $last = $middle - 1; | $last = $middle - 1; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| last = middle - 1; | last = middle - 1; | ||
| </code> | </code> | ||
| + | </details> | ||
| Мы помним, что значения ''first'', ''last'' и ''middle'' совпадают, так что новое значение ''last'' окажется на единицу меньше ''first''. Ситуация кажется странной — как последнее слово может находиться перед первым? | Мы помним, что значения ''first'', ''last'' и ''middle'' совпадают, так что новое значение ''last'' окажется на единицу меньше ''first''. Ситуация кажется странной — как последнее слово может находиться перед первым? | ||
| Строка 645: | Строка 678: | ||
| Такая же ситуация возникнет, если слово-кандидат будет больше среднего слова, но там сработает вторая ветка: | Такая же ситуация возникнет, если слово-кандидат будет больше среднего слова, но там сработает вторая ветка: | ||
| - | <code> | + | <code javascript> |
| first = middle + 1; | first = middle + 1; | ||
| </code> | </code> | ||
| - | Python | ||
| - | <code> | + | <details> |
| + | <summary>Python</summary> | ||
| + | |||
| + | <code python> | ||
| first = middle + 1 | first = middle + 1 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| $first = $middle + 1; | $first = $middle + 1; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| first = middle + 1; | first = middle + 1; | ||
| </code> | </code> | ||
| + | </details> | ||
| Цикл следует остановить, когда левая граница станет больше правой. Но в операторе ''while'' мы записываем не условие остановки цикла, а условие продолжения, поэтому условие надо поменять на обратное: ''first <= last''. Если цикл завершается и кандидат в списке не найден, значит, поиск завершился неудачно — алгоритм вернет ''false'': | Цикл следует остановить, когда левая граница станет больше правой. Но в операторе ''while'' мы записываем не условие остановки цикла, а условие продолжения, поэтому условие надо поменять на обратное: ''first <= last''. Если цикл завершается и кандидат в списке не найден, значит, поиск завершился неудачно — алгоритм вернет ''false'': | ||
| - | <code> | + | <code javascript> |
| // пока область поиска не пуста | // пока область поиска не пуста | ||
| while (first <= last) { | while (first <= last) { | ||
| Строка 680: | Строка 720: | ||
| </code> | </code> | ||
| - | Python | ||
| - | <code> | + | <details> |
| + | <summary>Python</summary> | ||
| + | |||
| + | <code python> | ||
| # пока область поиска не пуста | # пока область поиска не пуста | ||
| while first <= last: | while first <= last: | ||
| Строка 689: | Строка 731: | ||
| return False | return False | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 702: | Строка 746: | ||
| return false; | return false; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| // пока область поиска не пуста | // пока область поиска не пуста | ||
| while (first <= last) { | while (first <= last) { | ||
| Строка 711: | Строка 757: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| ==== Недостатки бинарного поиска ==== | ==== Недостатки бинарного поиска ==== | ||
| Строка 724: | Строка 771: | ||
| И третье ограничение — некоторые данные просто нельзя упорядочить. Например, не существует какого-то естественного общепризнанного способа упорядочить цвета: | И третье ограничение — некоторые данные просто нельзя упорядочить. Например, не существует какого-то естественного общепризнанного способа упорядочить цвета: | ||
| - | {{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjNlY2RiNmFmZTNiZjU5NGJhYTE3YWQwNTI4ODJhZTJhLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=79405509d9f406a665a6eeb6edffe0ff249c44e89dcc7b9a3f1c7e00ec3a91cc|Цвета}}Таким же образом, сложно упорядочить пары чисел. Возьмем для примера широту и долготу — это как раз пара чисел: | + | {{ :basics_of_algorithms:image_processing20231003-35-vql2f3.png |}} |
| + | |||
| + | Таким же образом, сложно упорядочить пары чисел. Возьмем для примера широту и долготу — это как раз пара чисел: | ||
| * Самый западный город России — Балтийск, его координаты 54°39′ с. ш. 19°55′ в. д. | * Самый западный город России — Балтийск, его координаты 54°39′ с. ш. 19°55′ в. д. | ||
| Строка 770: | Строка 819: | ||
| * У метода перебора есть два варианта: Простой перебор, чтобы проверить, есть ли элемент в списке | * У метода перебора есть два варианта: Простой перебор, чтобы проверить, есть ли элемент в списке | ||
| - | ===== Для полного доступа к курсу нужен базовый план ===== | ||
| - | |||
| - | Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент. | ||
| - | |||
| - | [[:subscription:new?nickname=professional_monthly_3900|Получить доступ]] | ||
| - | |||
| - | ---- | ||
| - | |||
| - | 130 | ||
| - | |||
| - | [[:courses|курсов]] | ||
| - | |||
| - | 1000 | ||
| - | |||
| - | упражнений | ||
| - | |||
| - | 2000+ | ||
| - | |||
| - | часов теории | ||
| - | |||
| - | 3200 | ||
| - | тестов | ||
basics_of_algorithms/binary_search.1696350178.txt.gz · Последние изменения: 2023/10/03 19:22 — werwolf
Инструменты страницы
Если не указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: CC Attribution-Share Alike 4.0 International
