В алгоритме для медианы двух отсортированных массивов разных размеров за время lg (n).
Основной шаг - найти раздел таким образом, чтобы все элементы слева были менее чем равны всем элементам справа от раздела.
Я пытался предположить, что такого раздела не существует, поэтому для каждого возможного индекса раздела мы имеем
Условие: arr1 [слева]> arr2 [справа] или arr1 [справа]
Но я не могу показать, что всегда будет существовать индекс, содержащий условие false.