Двоичный поиск

Угадай число
Загадано число от 1 до 100, используя подсказки больше-меньше угадайте число.
За какое число попыток можно гарантированно угадать число?

Угадай число
За какое число попыток можно гарантированно угадать число из интервала от 1 до 100?

Угадай число
За какое число попыток можно гарантированно угадать число из интервала?

Двоичный (бинарный) поиск
метод деления пополам - самый быстрый поиск по упорядоченному набору данных
Задать левую границу поиска
Задать правую границу поиска
Найти середину интервала
Сравнить середину с искомым значением
Перейти в левую или правую часть в зависимости от результата сравнения
Повторить с первого пункта

Двоичный поиск
Заданы номера выигрышных лотерейных билетов. Определить является ваш билет выигравшим 50?

Двоичный поиск
l=0; r=n;
while (l
{
m=(l+r)/2;
if (a[m]
else r=m;
}
if (a[l]==k) // найден
else // не найден

Двоичный поиск
(с поддержкой инварианта)
l=0; r=n; // полуинтервал [0; n)
инвариант
while (l+1
{
m=(l+r)/2;
if (a[m]<=k) l=m; // инвариант [ ; )
else r=m;
}
if (a[l]==k) // найден // инвариант [ ; )
else // не найден

Двоичный поиск
(с повторяющимися элементами)
l=0; r=n;
while (l+1
{
m=(l+r)/2;
if (a[m]<=k) l=m;
else r=m;
}
if (a[l]==k) // найден
else // не найден
1 1 1 3 3 3 5 5 5 7 7 8 8 8
находит самое правое вхождение