Найти медиану двух отсортированных массивов разного размера в сложности O (min (log (n), log (m)))

Прежде чем ответить, пожалуйста, имейте в виду, что оба массива имеют разный размер и запрошенная сложность O (min (log (n), log (m))), этот вопрос никогда не задавался в стеке потока.

Я пытался изменить решение O (log (n + m)) для работы, но не смог, следующее решение ищет элемент kth (медиана объединенного массива), но сложность log (n + m) ,

Чтобы решить эту проблему в O (min (log (n), log (m))), нам нужно вырезать также k / 2 элементов второго массива при каждом вызове рекурсии.

Обновленный код:

int select(int *a, int *b, int sa, int sb, int k) {
int ma = sa < k/2 ? sa - 1 : k/2 - 1;
int mb = k - ma - 2;
if (sa + sb < k)
return -1;
if (sa == 0)
return b[k - 1];
if (sb == 0)
return a[k - 1];
if (k == 1)
return a[0] < b[0] ? a[0] : b[0];
if (a[ma] == b[mb])
return a[ma];
if (a[ma] < b[mb])
return select(a + ma + 1, b, sa - ma - 1, mb + 1, k - ma - 1);
return select(a, b + mb + 1, ma + 1, sb - mb - 1, k - mb - 1);
}

/*
median:
uses select to find the median of the union of a and b (where a and b are sorted
positive integer arrays of sizes sa and sb respectively).
*/
int median(int *a, int *b, int sa, int sb) {
int m1, m2;
if ((sa + sb) % 2 == 1)
return select(a, b, sa, sb, (sa + sb)/2 + 1);
return select(a, b, sa, sb, (sa + sb)/2);

}

int main() {
int a[3] = {2, 4, 6};
int b[11] = {1, 3, 5, 7, 13, 17, 22, 23, 24, 25, 31};
printf("\n median is %d\n", median(a, b, 3, 11));
return 0;
}

Я пытаюсь доказать временную сложность и основательность алгоритма без удачи.