Различия

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

--- basics_of_algorithms:binary_search [2023/10/03 19:05]
werwolf [Недостатки бинарного поиска]
+++ basics_of_algorithms:binary_search [2023/10/03 19:43] (текущий)
werwolf [Как реализовать бинарный поиск]
@@ Строка 1: / Строка 1: @@
-==== Недостатки бинарного поиска ====
+====== Бинарный поиск — Основы алгоритмов и структур данных ======
+Мы постоянно что-то ищем с помощью компьютера: номера телефона, свободные номера в гостиницах, товары в интернет-магазинах, квартиры в аренду. Даже сайты мы ищем с помощью поисковой машины. За каждым из этих поисков скрываются разные алгоритмы. Среди них — поиск подстроки, поиск по ключевым словам, префиксный поиск.
+В этом уроке мы познакомимся с двумя алгоритмами — **методом перебора** и **бинарным поиском**.
+===== Метод перебора =====
+Алгоритм перебора проверяет все значения в списке с начала и до нужного атрибута, поэтому его также называют **последовательным** или **линейным поиском**.
+Начнем с самого простого алгоритма перебора — **поиска по списку**.
+Представим, что мы хотим найти в Google все страницы, на которых встречается фраза «А роза упала на лапу Азора». Слова «роза», «упала» и «лапа» встречаются редко и только в этой фразе, поэтому они значимы для поиска.
+А вот слова «а» и «на» встречаются в огромном количестве других запросов и в самых разных предложениях. На результаты поиска они не влияют, потому что поисковые машины исключают их из запроса.
+Поисковик примет фразу «а роза упала на лапу Азора» и превратит ее в «роза упала лапу Азора». Таким образом он уберет из запроса **стоп-слова**. К ним относятся союзы, частицы, предлоги, междометия и некоторые другие части речи.
+У каждой поисковой машины есть свой список стоп-слов, которые она автоматически исключает из текста. Для примера возьмем такой список стоп-слов в случайном порядке:
+| или | вас | для | после | ого | раньше |
+| но | ее | на | во | эх | позже |
+| дабы | что | по | не | браво | когда-то |
+| затем | который | со | же | здравствуйте | очень |
+| потом | их | из | то | спасибо | минимально |
+| лишь | все | от | бы | извините | максимально |
+| только | они | до | всего | что-то | а |
+| он | я | без | итого | какой-то | огромный |
+| мы | весь | над | даже | где-то | предельно |
+| его | мне | под | да | как-то | сильно |
+| вы | меня | за | нет | дальше | слабо |
+| вам | таким | при | ой | ближе | самый |
+Сейчас таблица неудобная — в ней нет какого-либо порядка. Чтобы найти нужное слово, придется постоянно просматривать весь список, тратить время и силы. Работа пойдет быстрее и проще, если упорядочить слова по алфавиту. Слова упорядочены по колонкам:
+| а | где-то | здравствуйте | меня | он | самый |
+| без | да | из | минимально | они | сильно |
+| ближе | дабы | извините | мне | от | слабо |
+| браво | даже | или | мы | очень | со |
+| бы | дальше | итого | на | по | спасибо |
+| вам | для | их | над | под | таким |
+| вас | до | как-то | не | позже | то |
+| весь | его | какой-то | нет | после | только |
+| во | ее | когда-то | но | потом | что |
+| все | же | который | ого | предельно | что-то |
+| всего | за | лишь | огромный | при | эх |
+| вы | затем | максимально | ой | раньше | я |
+Рассмотрим более сложный вариант метода перебора — **поиск по ключу**. Такой алгоритм помогает узнать, встречается ли искомое слово в нашем списке. Для примера возьмем массив с европейскими столицами и датами их основания:
+| 1804 | Вена | 1237 | Берлин | 1323 | Вильнюс |
+| 1614 | Тирана | 1167 | Копенгаген | 963 | Люксембург |
+| 1067 | Минск | 1191 | Дублин | 1275 | Амстердам |
+| 752 | Ватикан | 1786 | Рейкьявик | 1200 | Варшава |
+| 1872 | Будапешт | 856 | Мадрид | 1147 | Москва |
+Какой город основали в 1275 году? Чтобы ответить, придется перебрать все записи в списке, потому что они расположены в случайном порядке.
+Упорядочим города по году основания, и тогда ответ будет очевиден:
+| 752 | Ватикан | 1167 | Копенгаген | 1323 | Вильнюс |
+| 856 | Мадрид | 1191 | Дублин | 1614 | Тирана |
+| 963 | Люксембург | 1200 | Варшава | 1786 | Рейкьявик |
+| 1067 | Минск | 1237 | Берлин | 1804 | Вена |
+| 1147 | Москва | 1275 | Амстердам | 1872 | Будапешт |
+Эти два примера показывают нам два варианта поиска по списку:
+  * В примере со стоп-словами мы проверяли, есть ли слово в списке. Это самый простой вид поиска
+  * В примере со столицами мы знали один **атрибут** города — год основания, и мы хотели узнать другой атрибут — название. Атрибут, по которому мы ищем, называется **ключом**, а сам метод — **поиском по ключу**
+По обоим примерам видно, насколько медленно работает метод перебора. В худшем случае алгоритму придется проверить практически все значения в списке.
+Представим, что по такому методу работает проверка логина и пароля в Facebook. Массив с логинами-паролями всех пользователей содержит около трех миллиардов элементов. Даже на самых быстрых серверах поиск в массиве занимал бы несколько минут.
+Чтобы не тратить так много времени на авторизацию в Facebook и работу с другими массивами, можно использовать более быстрый алгоритм.
+===== Как ускорить алгоритм перебора =====
+Мы без труда находим нужную информацию в справочниках и словарях, потому что в них словарные статьи упорядочены. Чтобы работать с такими массивами, люди пользуются неким алгоритмом. Сложность в том, что это происходит на интуитивном уровне — формально описать такой алгоритм непросто.
+В то же время компьютеру нужны конкретные инструкции, так что нам придется превратить интуитивное знание в алгоритм.
+Чтобы это сделать, начнем с простого метода перебора:
+<code javascript>
+const stopWords = ['ее', 'на', 'по', 'со', 'же', 'браво', 'всего', 'я', 'итого'];
+const isStopWord = (candidate) => {
+  for (let i = 0; i < stopWords.length; i += 1) {
+    if (stopWords[i] === candidate) {
+      return true;
+    }
+  }
+  return false;
+};
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+stop_words = ['ее', 'на', 'по', 'со', 'же', 'браво', 'всего', 'я', 'итого']
+def is_stop_word(stop_words, candidate):
+    for i in range(len(stop_words)):
+        if stop_words[i] == candidate:
+            return True
+    return False
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code php>
+<?php
+$stopWords = ['ее', 'на', 'по', 'со', 'же', 'браво', 'всего', 'я', 'итого'];
+function isStopWord($stopWords, $candidate)
+{
+  foreach ($stopWords as $word) {
+    if ($word === $candidate) {
+      return true;
+    }
+  }
+  return false;
+}
+</code>
+</details>
+<details>
+<summary>Java</summary>
+<code java>
+class App {
+    private static List<String> stopWords = List.of(
+        "ее", "на", "по", "со", "же", "браво", "всего", "я", "итого"
+    );
+    public static boolean isStopWord(String candidate) {
+        for(String word : stopWords) {
+            if (word.equals(candidate)) {
+                return true;
+            }
+        }
+        return false;
+    }
+}
+</code>
+</details>
+Функция ''isStopWord()'' перебирает **слова-кандидаты**, последовательно сравнивает их с каждой строкой в массиве стоп-слов и возвращает ''true'' или ''false''. Мы вставили сюда слова из нашей таблицы, но, чтобы код не получился слишком большим, ограничились десятком слов.
+Разберемся, почему такой поиск работает медленно. На каждом шаге функция двигается к соседнему слову в массиве, чтобы его проверить. В худшем случае она проверяет все слова.
+Чтобы ускорить работу, нужно отбрасывать куски массива, где нужного слова точно нет. Пока это невозможно: элементы массива расположены в произвольном порядке, поэтому нужное нам слово может быть где угодно.
+Другое дело упорядоченный массив: в нем слова отсортированы по алфавиту. Мы можем не перебирать все элементы, а постепенно отбрасывать лишние фрагменты массива и быстрее искать стоп-слова. В этом поможет **бинарный поиск**.
+===== Бинарный поиск =====
+Бинарный поиск — это метод поиска, при котором алгоритм ищет элементы в ограниченной области поиска, причем с каждым шагом область поиска делится на две части.
+Кратко опишем механизм работы бинарного поиска:
+  * Бинарный поиск начинается со среднего элемента и на первом шаге идет по всему массиву
+  * На каждом шаге область поиска делится пополам, при этом границы поиска задаются первым и последним элементом
+  * Алгоритм завершается, когда область поиска сужается до одного элемента
+Теперь посмотрим, как выглядит бинарный поиск в нашем примере со стоп-словами.
+Алгоритм начинается с середины — это слово «который».
+Очевидно, что перед ним нет слов «предельно» или «чтобы» — ведь буквы П и Ч в алфавите следуют за К. Если ищем слово «очень», то можем отбросить все слова перед «который» — это практически половина словаря.
+Мы определили, что слово-кандидат может находиться только во второй половине списка. Рядом с К находятся буквы Л и М, так что поблизости от «который» могут быть только слова «лишь» и «мне». Буква О стоит далеко, поэтому и слово «очень» надо искать далеко. Так что заглядываем далеко вперед и попадаем, скажем, на слово «потом».
+Ситуация со словом «который» повторяется. Теперь О находится перед П, так что мы можем отбросить все слова после «потом».
+Если мы отбросим все слова перед «который» и после «потом», в нашем распоряжении останется всего четверть от первоначального списка:
+| который | ого |
+| лишь | огромный |
+| максимально | ой |
+| меня | он |
+| минимально | они |
+| мне | от |
+| мы | очень |
+| на | по |
+| над | под |
+| не | позже |
+| нет | после |
+| но | |
+Теперь у нас есть **область поиска**. Сначала в область поиска входит весь список, но на каждом шаге она сокращается вдвое. Область поиска можно задать, указав на первое и последнее слово.
+Алгоритм заканчивает работу, когда область поиска сужается до одного слова. Если это наше слово-кандидат, значит поиск завершился успешно.
+==== Как реализовать бинарный поиск ====
+Выше мы описали алгоритм — осталось только превратить его в программу. Формализуем каждый шаг так, чтобы его мог выполнить компьютер.
+Вот функция, которая проверяет, есть ли стоп-слово в отсортированном массиве:
+<code javascript>
+const stopWords = ['а', 'без', 'ближе', 'браво', 'бы', 'вам', 'вас', 'весь', 'во', 'все', 'всего', 'вы'];
+const isStopWord = (candidate) => {
+  // индекс первого элемента области поиска
+  let first = 0;
+  // индекс последнего элемента области поиска
+  let last = stopWords.length - 1;
+  // пока область поиска не пуста
+  while (first <= last) {
+    // индекс среднего элемента области поиска
+    const middle = Math.floor((first + last) / 2);
+    if (candidate === stopWords[middle]) {
+      // если нашли слово-кандидат, поиск завершается удачно
+      return true;
+    }
+    if (candidate < stopWords[middle]) {
+      // если кандидат меньше, отбрасываем правую половину
+      last = middle - 1;
+    } else {
+      // если кандидат больше, отбрасываем левую половину
+      first = middle + 1;
+    }
+  }
+  return false;
+};
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+stop_words = ['а', 'без', 'ближе', 'браво', 'бы', 'вам', 'вас', 'весь', 'во', 'все', 'всего', 'вы']
+def is_stop_word(stop_words, candidate):
+    # индекс первого элемента области поиска
+    first = 0
+    # индекс последнего элемента области поиска
+    last = len(stop_words) - 1
+    while (first <= last):
+        # индекс среднего элемента области поиска
+        middle = (first + last) // 2
+        if candidate == stop_words[middle]:
+            # если нашли слово-кандидат, поиск завершается удачно
+            return True
+        if candidate < stop_words[middle]:
+            # если кандидат меньше, отбрасываем правую половину
+            last = middle - 1
+        else:
+            # если кандидат больше, отбрасываем левую половину
+            first = middle + 1
+    return False
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code php>
+<?php
+$stopWords = ['а', 'без', 'ближе', 'браво', 'бы', 'вам', 'вас', 'весь', 'во', 'все', 'всего', 'вы'];
+function isStopWord($candidate)
+{
+    $first = 0;
+    $last = count($stopWords) - 1;
+    while ($first <= $last) {
+        $middle = round(($first + $last) / 2);
+        if ($candidate === $stopWords[$middle]) {
+            return true;
+        }
+        if ($candidate < $stopWords[$middle]) {
+            $last = $middle - 1;
+        } else {
+            $first = $middle + 1;
+        }
+    }
+    return false;
+};
+</code>
+</details>
+<details>
+<summary>Java</summary>
+<code java>
+class App {
+    private static List<String> stopWords = List.of(
+        "а", "без", "ближе", "браво", "бы", "вам", "вас", "весь", "во", "все", "всего", "вы"
+    );
+    public static boolean isStopWord(String candidate) {
+        // индекс первого элемента области поиска
+        var first = 0;
+        // индекс последнего элемента области поиска
+        var last = stopWords.size() - 1;
+        // пока область поиска не пуста
+        while (first <= last) {
+            // индекс среднего элемента области поиска
+            var middle = (first + last) / 2;
+            if (candidate.equals(stopWords.get(middle))) {
+                // если нашли слово-кандидат, поиск завершается удачно
+                return true;
+            }
+            if (candidate.compareTo(stopWords.get(middle)) < 0) {
+                // если кандидат меньше, отбрасываем правую половину
+                last = middle - 1;
+            } else {
+                // если кандидат больше, отбрасываем левую половину
+                first = middle + 1;
+            }
+        }
+        return false;
+    }
+}
+</code>
+</details>
+Разберемся, как эта функция работает. На каждом шаге алгоритма мы взаимодействуем с областью поиска. Чтобы определить ее, нам достаточно хранить индексы его первого и последнего элементов. В самом начале область поиска совпадает со всем массивом.
+<code javascript>
+// индекс первого элемента области поиска
+let first = 0;
+// индекс последнего элемента области поиска
+let last = stopWords.length - 1;
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+# индекс первого элемента области поиска
+first = 0
+# индекс последнего элемента области поиска
+last = len(stop_words) - 1
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code php>
+<?php
+$first = 0;
+$last = count(stopWords) - 1;
+</code>
+</details>
+<details>
+<summary>Java</summary>
+<code java>
+// индекс первого элемента области поиска
+var first = 0;
+// индекс последнего элемента области поиска
+var last = stopWords.size() - 1;
+</code>
+</details>
+Элементы в массивах JavaScript нумеруются с нуля, поэтому сначала индекс первого элемента равен 0, а индекс последнего — на единицу меньше длины массива. Чтобы убедиться в этом, представьте массив, например, из четырех элементов: его элементы будут иметь индексы 0, 1, 2 и 3.
+На каждом шаге мы сравниваем слово-кандидат со словом из середины области. Найти среднее слово несложно: его индекс находится посередине между первым и последним словом.
+<code javascript>
+const middle = (first + last) / 2;
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+middle = (first + last) / 2
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code php>
+<?php
+$middle = ($first + $last) / 2
+</code>
+</details>
+<details>
+<summary>Java</summary>
+<code java>
+var middle = (first + last) / 2;
+</code>
+</details>
+В массиве с нечетным количеством элементов все просто: у нас есть центральный элемент и две равные половины слева и справа от него. В массиве с четным количеством элементов, длина левой и правой половин будет отличаться на единицу.
+В нашей формуле это будет означать, что ''first + last'' не делится нацело на 2.
+Чтобы справиться с этой ситуацией, мы округлим это значение вверх или вниз. Если вниз — левая половина будет на один элемент короче правой, а если вверх — наоборот. Можно выбрать любой вариант, алгоритм будет работать в обоих случаях. Округлим значение в меньшую сторону:
+<code javascript>
+// индекс среднего элемента области поиска
+const middle = Math.floor((first + last) / 2);
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+middle = (first + last) // 2
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code php>
+$middle = round(($first + $last) / 2);
+</code>
+</details>
+<details>
+<summary>Java</summary>
+<code java>
+// В Java для целых чисел используется целочисленное деление
+var middle = (first + last) / 2;
+</code>
+</details>
+Дальше есть три варианта развития событий.
+**Вариант 1:** Слово-кандидат может совпадать со средним словом — поиск завершен с положительным результатом.
+**Вариант 2:** Слово-кандидат может быть меньше слова из середины. Тогда надо отбросить все элементы справа и продолжать поиск только в левой части. На следующем шаге первое слово останется прежним, а последнее изменится. Последним словом в новой области поиска станет центральное слово из старой:
+<code javascript>
+last = middle;
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+last = middle
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code php>
+<?php
+$last = $middle;
+</code>
+</details>
+<details>
+<summary>Java</summary>
+<code java>
+last = middle;
+</code>
+<details>
+На самом деле мы можем не включать центральное слово в новую область. При проверке первого варианта мы убедились, что слово-кандидат с ним не совпадает. Новым последним словом будет то, которое находится слева от центрального:
+<code javascript>
+last = middle - 1;
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+last = middle - 1
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code php>
+<?php
+$last = $middle - 1;
+</code>
+<details>
+<details>
+<summary>Java</summary>
+<code java>
+last = middle - 1;
+</code>
+</details>
+**Вариант 3:** Слово-кандидат может быть больше центрального слова. Тогда вместо правой границы надо двигать левую. Код окажется очень похожим:
+<code javascript>
+first = middle + 1;
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+first = middle + 1
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code>
+<?php
+$first = $middle + 1;
+</code>
+</details>
+<details>
+<summary>Java</summary>
+<code java>
+first = middle + 1;
+</code>
+</details>
+Мы сократили область поиска вдвое, а теперь надо повторить предыдущие шаги — тогда в нашей программе появится цикл:
+<code javascript>
+while (???) {
+  // индекс среднего элемента области поиска
+  const middle = Math.floor((first + last) / 2);
+  if (candidate === stopWords[middle]) {
+    // если нашли слово-кандидат, поиск завершается удачно
+    return true;
+  }
+  if (candidate < stopWords[middle]) {
+    // если кандидат меньше, отбрасываем правую половину
+    last = middle - 1;
+  } else {
+    // если кандидат больше, отбрасываем левую половину
+    first = middle + 1;
+  }
+}
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+while (???):
+    # индекс среднего элемента области поиска
+    middle = (first + last) // 2
+    if candidate == stop_words[middle]:
+        # если нашли слово-кандидат, поиск завершается удачно
+        return True
+    if candidate < stop_words[middle]:
+        # если кандидат меньше, отбрасываем правую половину
+        last = middle - 1
+    else:
+        # если кандидат больше, отбрасываем левую половину
+        first = middle + 1
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code php>
+<?php
+while (???) {
+    // индекс среднего элемента области поиска
+    $middle = round(($first + $last) / 2);
+    if ($candidate === $stopWords[$middle]) {
+        // если нашли слово-кандидат, поиск завершается удачно
+        return true;
+    }
+    if ($candidate < $stopWords[$middle]) {
+        // если кандидат меньше, отбрасываем правую половину
+        $last = $middle - 1;
+    } else {
+        // если кандидат больше, отбрасываем левую половину
+        $first = $middle + 1;
+    }
+}
+</code>
+</details>
+<details>
+<summary>Java</summary>
+<code java>
+while (???) {
+    // индекс среднего элемента области поиска
+    var middle = (first + last) / 2;
+    if (candidate.equals(stopWords.get(middle))) {
+        // если нашли слово-кандидат, поиск завершается удачно
+        return true;
+    }
+    if (candidate.compareTo(stopWords.get(middle)) < 0) {
+        // если кандидат меньше, отбрасываем правую половину
+        last = middle - 1;
+    } else {
+        // если кандидат больше, отбрасываем левую половину
+        first = middle + 1;
+    }
+    }
+</code>
+</details>
+Мы пока не знаем условия завершения цикла, поэтому написали три знака вопроса. Чтобы разобраться с условием, обратим внимание, что на каждом шаге первое и последнее слово двигаются к друг другу и когда-нибудь они совпадут. Тогда условие ''first === last'' станет истинным.
+Если ''first === last'', то формулу ''(first + last) / 2'' можно записать двумя способами:
+  * ''(first + first) / 2''
+  * ''(last + last) / 2''
+Индекс центрального элемента в любом случае будет равен ''first'' и ''last''.
+Слово-кандидат либо будет совпадать с центральным словом, либо нет. Если оно окажется меньше, у нас выполнится ветка:
+<code javasript>
+last = middle - 1;
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+last = middle - 1
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code php>
+<?php
+$last = $middle - 1;
+</code>
+</details>
+<details>
+<summary>Java</summary>
+<code java>
+last = middle - 1;
+</code>
+</details>
+Мы помним, что значения ''first'', ''last'' и ''middle'' совпадают, так что новое значение ''last'' окажется на единицу меньше ''first''. Ситуация кажется странной — как последнее слово может находиться перед первым?
+Так бывает в **вырожденных случаях** — массивах без элементов для сравнения и с пустой областью поиска. При последнем сравнении слово-кандидат не совпало со словом из списка — значит, его вообще не было в списке.
+Такая же ситуация возникнет, если слово-кандидат будет больше среднего слова, но там сработает вторая ветка:
+<code javascript>
+first = middle + 1;
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+first = middle + 1
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code php>
+<?php
+$first = $middle + 1;
+</code>
+</details>
+<details>
+<summary>Java</summary>
+<code java>
+first = middle + 1;
+</code>
+</details>
+Цикл следует остановить, когда левая граница станет больше правой. Но в операторе ''while'' мы записываем не условие остановки цикла, а условие продолжения, поэтому условие надо поменять на обратное: ''first <= last''. Если цикл завершается и кандидат в списке не найден, значит, поиск завершился неудачно — алгоритм вернет ''false'':
+<code javascript>
+// пока область поиска не пуста
+while (first <= last) {
+  // ...
+}
+return false;
+</code>
+<details>
+<summary>Python</summary>
+<code python>
+# пока область поиска не пуста
+while first <= last:
+    # ...
+return False
+</code>
+</details>
+<details>
+<summary>PHP</summary>
+<code php>
+<?php
+// пока область поиска не пуста
+while ($first <= $last) {
+    // ...
+}
+return false;
+</code>
+</details>
+<details>
+<summary>Java</summary>
+<code java>
+// пока область поиска не пуста
+while (first <= last) {
+    // ...
+}
+</code>
+</details>
+==== Недостатки бинарного поиска ====
 На примере списка стоп-слов сравним метод перебора и бинарный поиск. Первое заметное отличие — **бинарный поиск сложнее в реализации**. В нашем случае сортировка метода перебора занимает 8 строк, а бинарный поиск — 18 строк. Стоит ли писать такие сложные программы? Да, если мы ищем по массиву из ста элементов и более.
@@ Строка 13: / Строка 771: @@
 И третье ограничение — некоторые данные просто нельзя упорядочить. Например, не существует какого-то естественного общепризнанного способа упорядочить цвета:
-{{https://cdn2.hexlet.io/derivations/image/original/eyJpZCI6IjNlY2RiNmFmZTNiZjU5NGJhYTE3YWQwNTI4ODJhZTJhLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9|Цвета}} Таким же образом, сложно упорядочить пары чисел. Возьмем для примера широту и долготу — это как раз пара чисел:
+{{ :basics_of_algorithms:image_processing20231003-35-vql2f3.png |}}
-  * Самый западный город России — Балтийск, его координаты 54°39′ с. ш. 19°55′ в. д.
+Таким же образом, сложно упорядочить пары чисел. Возьмем для примера широту и долготу — это как раз пара чисел:
-  * Самый северный — Певек, координаты 69°42′ с. ш. 170°19′ в. д.
+  * Самый западный город России — Балтийск, его координаты 54°39′ с. ш. 19°55′ в. д.
+  * Самый северный — Певек, координаты 69°42′ с. ш. 170°19′ в. д.
 Какие координаты больше? Если бы речь шла только о широте или долготе, мы бы без труда ответили. Но здесь пара чисел: при сравнении широта может оказаться больше, а долгота меньше. Нельзя сказать, что широта важнее долготы или наоборот. Поэтому у координат и других пар чисел нет какого-то естественного и очевидного порядка.
@@ Строка 38: / Строка 798: @@
 Лучшим для бинарного поиска также окажется один цикл. В худшем случае бинарный поиск пройдет четыре цикла:
   * Первый поиск — целый массив из 10 элементов
   * Второй — подмассив из пяти элементов
   * Третий — подмассив из двух элементов
   * Четвертый — подмассив с одним последним элементом
 В итоге среднее число циклов для бинарного поиска — 2.
@@ Строка 48: / Строка 808: @@
 ^Размер^Перебор, среднее^Бинарный поиск, среднее|
-|10|5|2|
+| 10 | 5 | 2 |
-|1 000|500|5|
+| 1 000 | 500 | 5 |
-|1 000 000|500 000|10|
+| 1 000 000 | 500 000 | 10 |
 Как видим, разница в производительности колоссальная, особенно на больших массивах.
@@ Строка 56: / Строка 816: @@
 ===== Заключение =====
   * В уроке мы рассмотрели два алгоритма: метод перебора и бинарный поиск
   * У метода перебора есть два варианта: Простой перебор, чтобы проверить, есть ли элемент в списке
-===== Для полного доступа к курсу нужен базовый план =====
-Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
-[[:subscription:new?nickname=professional_monthly_3900|Получить доступ]]
-----
-[[:courses|курсов]]
-упражнений
-часов теории
-тестов
-\\

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

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

Различия

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