Метод дихотомии: различия между версиями

Докажите, что «варьирование» числа вопросов, которое мы наблюдали в примере с «не всегда обязательным» четвёртым вопросом, возможно тогда и только тогда, когда число возможных вариантов не является степенью двойки<ref>Подсказка: докажите вначале, что тот факт, что число возможных вариантов не является степенью двойки, является необходимым и достаточным условием появления на некотором шаге нечётного числа элементов, из которых нужно выбирать.</ref>.

 

 

Пусть мы имеем упорядоченный по неубыванию массив <math>M</math> из, скажем, <math>10^6</math> элементов. Нам необходимо найти индекс <math>i</math> элемента, значение которого равно <math>x</math>: