У планшета есть преимущество — он позволяет, например, легко делать пометки к своим записям или pdf-кам. Кроме того, нужен и другой функционал планшета. Просто он более-менее одинаков для всех, поэтому критерием будет именно возможность писать.
Тогда вся лекция будет состоять из фотографий.
К тому же у лектора свои обозначения, у меня — свои. Переконвертировать один раз при зарисовке, когда еще помню объяснение, можно, а каждый раз — сложно.
Да, на клавиатуре быстро писать формулы не получится.
Но, как я написал, есть планшет, на котором писать удобно (по крайне мере, мне).
А планшет дает и некоторые преимущества по сравнению с ручкой и тетрадью.
Быстрее всего будет так:
1. Делаем бинарный поиск, следя чтобы оба числа оставались на отрезке, пока это возможно.
2. У нас есть отрезок, середина которго правее меньшего числа и левее правого. Делаем по нему два бинпоиска.
Можно оценить экономию: с вероятностью 1/2 (разные половины исходного отрезка) экономим 1 операцию, с вероятностью 1/4 (одна половина, разные четверти) — 2, с вероятностью 1/8 — 3 и т.д. Сумма равна 2.
Этот же способ экономит Log(n) — Log(3/4n) = Log(4/3) ~ 0.4150374992788437 операций.
Впрочем, даже на ACM экономить 2 операции сравнения в бинпоиске вряд ли придется.