Если же не думать о том, что массивы могут не поместиться в памяти, то всё ещё проще. Простейший бинарный поиск: сдвигаем итератор сначала на m/2, потом на m/4, пока не дойдём до нужного элемента.
Подробнее: сравниваем (m/2)-е элементы массивов. В массиве с меньшим элементом сдвигаем начало на (m/2) и проделываем то же самое с (m/4), пока не дойдём до 1. Voila!
Как я и писал ниже, необязательно просматривать аж половину массивов. Достаточно взять кусок приемлемой длины и просматривать последний элемент.
Пример: два массива, оба длиной 1000 элементов. Берём, скажем, 100-й элемент каждого. Сравниваем. Тот, что меньше - отбрасываем, 100 элементов прошли, берём 200-й элемент и так далее. Доходим, до 900-го элемента, и уже теперь ищем медиану (1000-й элемент) в одном из кусков по предложенному методу.
Оптимальный размер кусков - корень из номера позиции медианы. То есть, для данного примера ~31. В таком случае нужно будет провести порядка 70 сравнений. Против 1000 в вашем случае.
P.s. Чётность суммы не означает чётности слагаемых.
flash_back: На самом деле, с иходным вопросом тоже можно работать. Тогда придётся изменять условие и решение станеть чуть более громоздким. Но вопрос можно изменять, как я понимаю, посколько он приведён лишь в качестве примера.
Весьма странная конструкция с преобразованием в целое суммы двух вещественных чисел. Использование целых в данном случае не снижает точности. Старайтесь избавляться от подобных вещей.
Василий: Это отличная книга, но она не подходит для начинающих, это совершенно точно. Слишком много текста. О чём говорить, если сортировка встречается только во втором томе? Это справочник, энциклопедия, библия, что угодно, но не учебник.
git cherry-pick <commit-SHA>