найти медиану из двух отсортированных массивов - я получаю исключение из stackoverflow

Question

Задача задана two sorted Arrays, найти median из двух в O(log n). слияние отсортированных массивов и поиск медианы (при n/2) должны работать. Но это O(n) времени, я думаю, и для этого требуется вспомогательное хранилище. Я нашел это pseudocode (проблема 2 в pdf). когда я реализую этот код, я получаю stackoverflow exception. Вот мой код:

public static int quickMedian(int[] arr1, int[] arr2, int startArr1, int endArr1, int startArr2, int endArr2){ 
     int m1=(endArr1-startArr1)/2; 
     int m2=(endArr2-startArr2)/2; 
     if (arr1[m1]==arr2[m2]) 
      return arr1[m1]; 
     if (arr1[m1]<arr2[m2]) 
      return quickMedian(arr1, arr2, m1, endArr1, startArr2, m2); 
     else 
      return quickMedian(arr1, arr2, startArr1, m1, m2, endArr2); 
    } 

public static void main (String[] args){ 
     int[] arr1={1,3,5,7}; 
     int[] arr2={2,4,6,8}; 
     int[] arr3={1,2,4,6,8,10,11}; 
     System.out.println(quickMedian(arr1, arr2, 0, arr1.length-1, 0, arr2.length-1)); 
    } 

мне нужна помощь фиксации stackoverflow exception и сделать эту работу. Благодарю.

Answer 1

Проблема заключается условие окончания

if (arr1[m1]==arr2[m2]) 
     return arr1[m1]; 

, поскольку она позволяет алгоритму работать бесконечно, если среднее значение не присутствует в обеих массивах. Поэтому метод quickMedian() вызывается снова и снова, пока вы не закончите пространство в стеке.

EDIT:

Я проанализировал псевдокод немного дальше, и я могу contently сказать, что алгоритм в корне ошибочным. Основной момент алгоритма состоит в том, чтобы взять два массива, разделить их на две части, отбросить половинки, которые не будут содержать медиану, а затем повторить для остальных массивов.

Проблема с этим подходом заключается в том, что, когда мы отбрасываем половинки массивов, которые не содержат медианы, мы остаемся с двумя массивами, которые содержат медиану, но не гарантировано, что медиана исходных массивов и половина из них будет одинаковой. Если один массив содержит больше элементов, чем другие, большее количество элементов будет отброшено из одного массива, и медиана новых массивов может сдвинуться.

a1 = {1,2,3,4,6,7,8,9} median = 6 
a2 = {5}     median = 5 

// median of a1 + a2 is 5 

После первого шага:

a3 = {1,2,3,4}   median = 3 
a4 = {5}     median = 5 

// median of a3 + a4 is 3 

медиана a3 + a4 теперь будет 3, поскольку три элемента выше, чем 5 были сняты, но не ниже элемента. Это правда, что медиана исходных массивов в двух новых массивах, но это не тот же элемент, что и медианный новых массивов. Поэтому этот рекурсивный метод не будет работать, независимо от того, сколько патчей и исправлений применяется. Поэтому я также предложил бы рассмотреть вопрос о слиянии двух массивов.

Answer 2

Хотя вы правильно внедрили код в решении PDF, решение плохое (для произвольного ввода).

У вас есть короткие массивы, так почему бы не пройтись по тому, что происходит?

главная:

quickMedian({1,3,5,7}, {2,4,6,8}, 0, 3, 0, 3) 

quickMedian: (1)

m1 = (3 - 0)/2 = 1 
m2 = (3 - 0)/2 = 1 
if (3 == 4)...// false 
if (3 < 4) quickMedian({1,3,5,7}, {2,4,6,8}, 1, 3, 0, 1) 
else...// unreached 

quickMedian: (2)

m1 = (3 - 1)/2 = 1 
m2 = (1 - 0)/2 = 0 
if (3 == 2)...// false 
if (3 < 2)...// false 
else quickMedian({1,3,5,7}, {2,4,6,8}, 1, 1, 0, 1) 

quickMedian: (3)

m1 = (1 - 1)/2 = 0 
m2 = (1 - 0)/2 = 0 
if (1 == 2)...// false 
if (1 < 2) quickMedian({1,3,5,7}, {2,4,6,8}, 0, 1, 0, 0) 
else...// unreached 

quickMedian: (4)

m1 = (1 - 0)/2 = 0 
m2 = (0 - 0)/2 = 0 
if (1 == 2)...// false 
if (1 < 2) quickMedian({1,3,5,7}, {2,4,6,8}, 0, 1, 0, 0) 
else...// unreached 

Как вы можете видеть, вызов quickMedian в 4-й итерации идентична той, в 3-й итерации , Вот где результат ломается.

---

Учитывая проблемы «здесь два отсортированных списков, найти среднее значение между ними обоими,» мой первый ответ был бы объединить списки и найти медиану в целом. Однако объединение двух отсортированных списков - это O (n), а не O (log n) в соответствии с запросом проблемы.

Answer 3

Вот O((logN)^2) алгоритма медианного поиска: -

1. взять в середину самого большого массива из двух
2. Найти индекс I чисел больше, чем середине в другом массиве с помощью бинарного поиска
3. Если ни один из элементов s до середины & i не превысит текущий k-й элемент, который будет найден, то медианный поиск по этим частям рекурсивно
4. else do median search for known = kold - s elemen t в остальных подмассивах.
5. Если осталось только 1 массив, то найдите k-й элемент в O (1).

псевдокод: -

void medianSearch(arr1,arr2,s1,s2,h1,h2,k) { 

    len1 = h1-s1+1; 
    len2 = h2-s2+1; 

    if(len1<=0||len2<=0) { 

    if(len2<=0) { 
      return(arr1[s1+k-1]); 
    } 

    else return(arr2[s2+k-1]); 
    } 

    if(len1>len2) { 

    int mid = (s1+h1)/2 
    int i = binSearch(arr2,s2,h2,arr1[mid]) 
    int size = i+mid-s1+2; 
    if(size>=k) { 
     return(medianSearch(arr1,arr2,s1,s2,mid,i,k)) 
    } 
    else { 

     return(medianSearch(arr1,arr2,mid+1,i+1,h1,h2,k-size)); 
    } 
    } 

    else { 

     // Use similar logic as first case. 
    } 

} 

Call:- medianSearch(arr1,arr2,0,0,M-1,N-1,(M+N)/2) 

Время Сложность: -

Каждая итерация уменьшает по крайней мере один массив до половины его размера Orignal. Каждая итерация принимает O (logN). Всего итераций будет O (logN), следовательно, T (N) = O ((logN)^2)