basics_of_algorithms:binary_search []

Эта страница только для чтения. Вы можете посмотреть её исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно.
====== Бинарный поиск — Основы алгоритмов и структур данных ======
Мы постоянно что-то ищем с помощью компьютера: номера телефона, свободные номера в гостиницах, товары в интернет-магазинах, квартиры в аренду. Даже сайты мы ищем с помощью поисковой машины. За каждым из этих поисков скрываются разные алгоритмы. Среди них — поиск подстроки, поиск по ключевым словам, префиксный поиск.

В этом уроке мы познакомимся с двумя алгоритмами — **методом перебора** и **бинарным поиском**.

===== Метод перебора =====

Алгоритм перебора проверяет все значения в списке с начала и до нужного атрибута, поэтому его также называют **последовательным** или **линейным поиском**.

Начнем с самого простого алгоритма перебора — **поиска по списку**.

Представим, что мы хотим найти в 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 строк. Стоит ли писать такие сложные программы? Да, если мы ищем по массиву из ста элементов и более.

Если нужно искать в небольших массивах, можно использовать метод перебора — он будет работать со сравнимой скоростью или даже быстрее.

Второе важное ограничение бинарного поиска — **массив всегда должен быть упорядоченным**. Со стоп-словами это ограничение не мешало, потому что это фиксированный список, который надо подготовить всего один раз.

Но если список не фиксированный и надо добавлять слова во время работы программы, тогда придется писать дополнительный сложный код. Мы не можем просто добавлять слова в конец массива, потому что это нарушит порядок.

И третье ограничение — некоторые данные просто нельзя упорядочить. Например, не существует какого-то естественного общепризнанного способа упорядочить цвета:

{{ :basics_of_algorithms:image_processing20231003-35-vql2f3.png |}}

Таким же образом, сложно упорядочить пары чисел. Возьмем для примера широту и долготу — это как раз пара чисел:

  * Самый западный город России — Балтийск, его координаты 54°39′ с. ш. 19°55′ в. д. 
  * Самый северный — Певек, координаты 69°42′ с. ш. 170°19′ в. д. 

Какие координаты больше? Если бы речь шла только о широте или долготе, мы бы без труда ответили. Но здесь пара чисел: при сравнении широта может оказаться больше, а долгота меньше. Нельзя сказать, что широта важнее долготы или наоборот. Поэтому у координат и других пар чисел нет какого-то естественного и очевидного порядка.

При этом всегда можно сравнить два цвета или две координаты и узнать, совпадают они или нет. Для таких данных будет работать метод перебора, которому достаточно проверки на равенство. Бинарный поиск не сработает, потому что ему нужно, чтобы данные были больше или меньше.

==== Преимущества бинарного поиска ====

Бинарный поиск быстрее метода перебора, но пока не обсудили, насколько именно он быстрее. Один из способов сравнить производительность на практике — написать программы и измерить время их выполнения.

А еще есть теоретический подход — можно сравнивать производительность с помощью рассуждений. Этот навык очень полезен, потому что позволяет отбрасывать плохие решения, не тратя время на разработку программы.

Сравним время поиска на массивах из 10, 1 000 и 1 000 000 элементов.

Что будем сравнивать? В обоих алгоритмах есть цикл. В одном случае он может выполняться 100 раз, а в другом — 50. Это значит, что второй цикл в два раза быстрее первого, хотя мы и не можем назвать точное время в секундах.

Проблема в том, что на разных данных количество циклов будет разным.

В массиве из десяти элементов можно найти число с первого раза, а можно — с десятого. В таких случаях принято считать среднее время выполнения, которое окажется где-то посередине. В среднем, в массиве из десяти элементов, метод перебора найдет нужное число за пять циклов.

Лучшим для бинарного поиска также окажется один цикл. В худшем случае бинарный поиск пройдет четыре цикла:

  * Первый поиск — целый массив из 10 элементов 
  * Второй — подмассив из пяти элементов 
  * Третий — подмассив из двух элементов 
  * Четвертый — подмассив с одним последним элементом 

В итоге среднее число циклов для бинарного поиска — 2.

Сведем результаты в одну таблицу:

^Размер^Перебор, среднее^Бинарный поиск, среднее|
| 10 | 5 | 2 |
| 1 000 | 500 | 5 |
| 1 000 000 | 500 000 | 10 |

Как видим, разница в производительности колоссальная, особенно на больших массивах.

===== Заключение =====

  * В уроке мы рассмотрели два алгоритма: метод перебора и бинарный поиск 
  * У метода перебора есть два варианта: Простой перебор, чтобы проверить, есть ли элемент в списке
Инструменты пользователя

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

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