Программируем

Пожалуйста, зарегистрируйтесь или войдите под уже созданным логином. Вы получите полный доступ ко всем статьям форума.

Join the forum, it's quick and easy

Программируем

Пожалуйста, зарегистрируйтесь или войдите под уже созданным логином. Вы получите полный доступ ко всем статьям форума.

Программируем

Вы хотите отреагировать на этот пост ? Создайте аккаунт всего в несколько кликов или войдите на форум.
Программируем

На нашем форуме программистов вы сможете найти софт для программирования и другие программы. На форуме обсуждаются многие языки программирования, задачи и их решения. Используются языки: C, Assembler, Pascal, Delphi, Flash и другие.

Последние темы

» Арена искусственных интеллектов Gridwars
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. EmptyСр Окт 12, 2016 2:43 am автор SeriousPasha

» требуется несколько JS разработчиков
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. EmptyПт Окт 07, 2016 10:19 pm автор mrktwn1

» Защита приложения от взлома
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. EmptyЧт Июн 18, 2015 10:28 pm автор stradi

» Ищите программиста или дизайнера?
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. EmptyПт Мар 27, 2015 6:25 am автор фриланс

» Создание и продвижение сайтов, их развитие.
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. EmptyСр Мар 25, 2015 12:40 am автор asdfghhgfdsa

» Исходники для студентов + скайп-консультации,помощь в написании программ
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. EmptyВт Окт 07, 2014 11:25 pm автор Horpion

» IT- технологии для развития бизнеса
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. EmptyПн Июн 23, 2014 6:11 pm автор dvos12

» Стенли Кубрик "С Широко закрытыми Глазами"
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. EmptyЧт Июн 12, 2014 2:01 am автор Vertuozzz

» Каталог популярных хостинг компаний
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. EmptyСб Май 10, 2014 7:18 pm автор naik

Самые активные пользователи

Aster (142)
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_leftБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. BarБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_right 
Exkalibur (89)
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_leftБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. BarБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_right 
Чебурашка (63)
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_leftБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. BarБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_right 
Administrator (34)
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_leftБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. BarБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_right 
ak95 (8)
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_leftБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. BarБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_right 
Пушкин (7)
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_leftБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. BarБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_right 
K4_ (7)
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_leftБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. BarБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_right 
LuDa (7)
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_leftБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. BarБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_right 
Goldcoding (6)
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_leftБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. BarБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_right 
Admin (6)
Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_leftБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. BarБинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Bar_right 

Партнеры

Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Top100 Rambler's Top100

    Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi.

    Aster
    Aster
    Admin
    Admin


    Сообщения : 142
    Очки : 274
    Репутация : 11
    Дата регистрации : 2010-01-07

    Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi. Empty Бинарный поиск(bin search)(Двоичный поиск) элемента в массиве. Pascal, Delphi.

    Сообщение автор Aster Вс Янв 10, 2010 4:15 pm

    Предположим, у нас есть массив a размерностью в 1000000 элементов и нам нужно в нем найти элемент key. Для простого, линейного поиска, эта задача решаема, но будет занимать довольно много времени. Именно для таких целей и существует бинарный поиск(bin Search).

    В чем заключается его принцип? Бинарный поиск работает только на отсортированном массиве.
    На каждом шаге мы берем средний элемент, затем сравниваем его с элементом левой и правом границы рассматриваемого участка(l, r). Соответственно, если элемент, который мы выбрали, оказывается меньше искомого, то можно отбросить левую часть рассматриваемого участка, так как и все элементы, которые там находятся будут меньше искомого.

    Пример:
    Ищем 15 в массиве: 6, 8, 9, 13, 15, 17.
    1 шаг: берем средний элемент, то есть 13.
    2 шаг: смотрим, больше ли этот элемент искомого, нет. Значит отбросим все элементы, идущие до среднего, так как они заведомо меньше(массив отсортирован!).
    3 шаг: Остались только числа 13, 15, 17. Берем средний элемент, и вот он, 15.

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

    Код:

        l := 1;
        r := n + 1;
        While l < r - 1 do
        begin
          m := (l + r) div 2;
          if a[m] > key then r := m
            else l := m;
        end;
        if a[l] = key then WriteLn(l);

    Этот код выдаст нам на экран номер искомого элемента, если такой имеется.

      Текущее время Пт Ноя 01, 2024 7:26 am