Дистанционная подготовка: zadacha #3
zadacha #3
от Madina - Вторник 31 Январь 2017, 21:20
3. Сложность двоичного поиска
  Zdravstvuite.
Hotelos by zametit, chto minimalnoe kolichestvo voprosov, trebuemoe dlya nahozhdeniya chisla x v diapazone ot 1 do 5 eto 2.
Algoritm:
m=(l+r)/2;
while(m!=n){
if(m>n){r=m-1;}
else{l=m+1;}

}
Tak zhe log(5)=2.
Chto ya ne uchla?
Re: zadacha #3
от Peter Cherepanov - Среда 1 Февраль 2017, 20:26
  Давайте думать вместе. у нас есть числа 1,2,3,4,5 .
Первый вопрос делит их на 2 группы. В одной группе будет 2 числа, в другой будет 3 числа. Разделить группу из 3 чисел за 1 вопрос невозможно. Значит всего нужно 3 вопроса.
Re: zadacha #3
от Евгений Егиоя - Четверг 16 Август 2018, 19:08
  Двоичный логарифм от N, с округлением в большую сторону.