Дистанционная подготовка: Не понимаю бинарный поиск.
Не понимаю бинарный поиск.
от Никита Пушкин - Вторник 26 Август 2014, 19:19
  Не могу понять реализацию бинарного поиска. Интересует вот этот момент:
while r>l do begin
    m:=(r+l) div 2;
    if a[m]<x then l:=m+1 else r:=m;
  end;
Почему левую границу сдвигают к m и прибавляют еще единицу, а праву просто приравнивают к m?
Re: Не понимаю бинарный поиск.
от Кундас Валерий - Воскресенье 31 Август 2014, 10:02
  потому что, для многих функций(и для данного решения тоже) усли (a[m]
Re: Не понимаю бинарный поиск.
от Тимофей Гутор - Воскресенье 31 Август 2014, 10:57
  Так уж получилось, что в бинпоиске левую границу включают, а правую нет - [l, r), чтобы ответ всегда был в l.