Блог пользователя iomaio

Бинпоиск
Автор iomaio, 13 лет назад, По-русски

Дорогие пользователи сайта codeforces я хотел изучить бинпоиск можете дать хороший материал?

Заранее благодарен!!!

  • Проголосовать: нравится
  • -25
  • Проголосовать: не нравится

»
13 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +4 Проголосовать: не нравится

Лучше сам попробуй реализовать, там ничего трудного нет. Идея то проста.

Ты ищешь некое число n в массиве num:
Если num[(l+r+1) div 2] >= n , тогда рекурсивно вызываешься еще раз, меняешь границы на 
(l,(l+r+1) div 2), если больше, то ((l+r+1) div 2,r);
В конце у тебя получится 2 элемента, там уже выберешь левый или правый возвращать.
(Зависит от того, какой знак у тебя стоит в сравнении, строгое неравенство или нет.)

l-левая граница массива(первый элемент, изначально). r-правая граница массива(последний). Лично я так реализовывал.

http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=2#1 Тут проверить можешь сразу.

_P.S. массив отсортирован по неубыванию._
→ Ответить
  • »
    »
    13 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится 
    Небольшое замечание:

Иногда (r + l) / 2 может переполнятся. Про это нужно не забывать. Ну и делать что-нибудь типа l + (r - l) / 2
    → Ответить
»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

while(r-l!=1)

{

if((r+l)/2<=x)

l=(r+l)/2;

else

r=(r+l)/2

}

Ответ в l

→ Ответить