Как за минимальное число шагов найти минимальное подходящее значение в заданном диапазоне? А максимальное? Есть известное мне множество A натуральных чисел с шагом 1.
Есть неизвестное мне множество B натуральных чисел с шагом 1, входящее в множество А.
Есть обработчик, который проверяет, входит ли подставленное в него число из множества А в множество B.
Как в этом случае за минимальное число шагов найти минимальное число из множества А, входящее в множество В?
Как в этом случае за минимальное число шагов найти максимальное число из множества А, входящее в множество В?

Предыдущий
вопрос Следующий
вопрос

Для поиска минимального числа из множества A, входящего в множество B, можно использовать бинарный поиск. Начнем проверку с середины диапазона значений множества A. Если это число входит в множество B, то можно сузить диапазон до левой половины иначе - до правой половины. Продолжать этот процесс до тех пор, пока не найдется минимальное подходящее число.

Для поиска максимального числа из множества A, входящего в множество B, можно также использовать бинарный поиск. Начнем проверку с середины диапазона значений множества A. Если это число входит в множество B, то можно сузить диапазон до правой половины иначе - до левой половины. Продолжать этот процесс до тех пор, пока не найдется максимальное подходящее число.

Таким образом, бинарный поиск позволит найти минимальное и максимальное число из множества A, входящее в множество B за минимальное число шагов.