<MyRusakov.ru />

Программирование на Python с Нуля до Гуру

Программирование на Python с Нуля до Гуру

Данный курс научит Вас программировать на языке Python, который крайне желательно знать любому, кто хоть иногда имеет дело с компьютерами. Курс состоит из 6 разделов, в которых Вы с нуля освоите этот язык и сможете создавать самые разные программы для самых разных задач любой сложности.

К курсу прилагается множество упражнений и все исходники из уроков.

Наконец, Вы получите ещё несколько бонусов: "Создание калькулятора на Python", "Создание игры на Python" и "Правильная работа со справочником".

Подробнее
Подписка

Подписавшись по E-mail, Вы будете получать уведомления о новых статьях.

Подписка Подписаться

Добавляйтесь ко мне в друзья ВКонтакте! Отзывы о сайте и обо мне оставляйте в моей группе.

Мой аккаунт Мой аккаунт Моя группа
Опрос

Каким движком Вы предпочитаете пользоваться?

Бинарный поиск в JavaScript

Бинарный поиск в JavaScript

В прошлой статье мы говорили с вами о линейном поиске, который подойдет для поиска в небольших по объему не сортированных коллекциях. Однако, на практике, часто приходиться работать с крупными структурами данных, для поиска в которых лучше подходит бинарный поиск.

Представим, что вы играете в игру, в которой необходимо отгадать некоторое число, например, от 1-го до 100. Вы выбираете произвольное число. Если выбранное вами число больше искомого или меньше него, то вы получает подсказку.

Какой будет ваша стратегия? Будете ли вы выбирать числа случайно? Начнете ли вы с 1, затем с 2 и так далее, пока не отыщете искомое число? Но, конечно, желательно, уменьшить время поиска насколько это возможно. Следовательно, числа можно начать угадывать с 50, т.е. с середины, тем самым сразу отбрасывая ненужную половину. Далее можно взять середину – 75 - из диапазона 50 – 100. Если искомое число меньше (о том, что число меньше вам известно из подсказки, само число не известно) , то это означает, что число находится в диапазоне от 50 до 75, в противном случае в диапазоне от 75 до 100. Таким образом, деля последовательность пополам на все более мелкие части, вы в итоге найдете искомое число. Примерно так и работает бинарный поиск.

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

Для поиска цифры 9 в списке:

1 2 3 4 5 6 7 8 9 10

сначала мы находим средний элемент. Этот элемент находится в позиции Math.floor ((first + last) / 2), где first - первый индекс (индексация массивов начинается с нуля), а last - последний индекс. Math.floor() – округляет значение до ближайшего меньшего целого числа. Средний элемент в этом списке равен 5. Наше искомое значение 9 больше 5, поэтому мы ищем интересующее нас значение в срезе списка:

6 7 8 9 10

Средний элемент этого среза равен 8. Девять больше, чем 8, поэтому продолжаем поиск в срезе коллекции:

9 10

Средний элемент равен 9, искомое значение найдено.

Реализация бинарного поиска в JavaScript

Теперь давайте реализуем алгоритм двоичного поиска в JavaScript!

Мы создадим функцию binarySearch, которая принимает значение, которое необходимо найти и массив, в котором этот поиск будет осуществляться. Функция вернет позицию значения в списке в случае успеха. Если значение не будет найдено, возвращается -1. Вот реализация:

function binarySearch(value, list) {

    let first    = 0;                // начальный индекс в массиве
    let last     = list.length - 1;  // конечный индекс
    let position = -1;
    let found    = false;
    let middle;


    while (found === false && first <= last) {

        middle = Math.floor((first + last) / 2);

        if (list[middle] == value) {
            found = true;
            position = middle;
        } else if (list[middle] > value){ // значение в нижней части списка
            last = middle - 1;
        } else {  // значение в верхней части списка
            first = middle + 1;
        }

    }

    return position;

}

Заключение

В этой и предыдущей статье мы рассмотрели, как реализовать линейный поиск и алгоритм двоичного поиска. Алгоритм линейного поиска проще и не требует отсортированного массива. Тем не менее, он неэффективен для использования с большими массивами. В худшем случае алгоритм должен будет искать все элементы, делая n сравнений (где n - количество элементов).

С другой стороны, алгоритм двоичного поиска требует, чтобы вы сначала отсортировали массив, и его сложнее реализовать. Тем не менее, он более эффективен, даже если учитывать стоимость сортировки. Например, для массива из 10 элементов будет сделано не более 4 сравнений в случае бинарного поиска против 10 для линейного поиска – здесь различие не очень существенно. Однако для массива с 1 000 000 элементов наихудший случай в бинарном поиске - всего 20 сравнений. Это огромное улучшение по сравнению с линейным поиском!

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

Копирование материалов разрешается только с указанием автора (Михаил Русаков) и индексируемой прямой ссылкой на сайт (http://myrusakov.ru)!

Добавляйтесь ко мне в друзья ВКонтакте: http://vk.com/myrusakov.
Если Вы хотите дать оценку мне и моей работе, то напишите её в моей группе: http://vk.com/rusakovmy.

Если Вы не хотите пропустить новые материалы на сайте,
то Вы можете подписаться на обновления: Подписаться на обновления

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

Порекомендуйте эту статью друзьям:

Если Вам понравился сайт, то разместите ссылку на него (у себя на сайте, на форуме, в контакте):

  1. Кнопка:

    Она выглядит вот так: Как создать свой сайт

  2. Текстовая ссылка:

    Она выглядит вот так: Как создать свой сайт

  3. BB-код ссылки для форумов (например, можете поставить её в подписи):

Комментарии (0):

Для добавления комментариев надо войти в систему.
Если Вы ещё не зарегистрированы на сайте, то сначала зарегистрируйтесь.