Позвольте мне помочь вам это визуализировать. Допустим, это случай 3, то же самое рассуждение следует и для другого случая. Это означает, что мы определили, что медиана присутствует в 1-й половине ar1 или во второй половине ar2. Теперь вопрос в том, почему медиана этих половинок такая же, как и медиана исходных массивов, верно.

Итак, визуализируйте, как соединить вместе только эти релевантные половинки в отсортированном порядке и найти медиану. Теперь поместите остальные оставшиеся половинки обратно на эту картинку, куда бы они пошли. Первая половина ar2, все n / 2 элементов должны быть на вершине этой новой медианы, а вторая половина arr1 все n / 2 элементов должны быть ниже этой медианы (точное расположение не имеет значения для медианы). Это означает, что оно все равно будет медианным, поскольку выше и ниже него добавляется равное количество элементов. Таким образом, медиана двух новых половинок такая же, как и медиана исходного набора.

Чтобы быть еще более точным, давайте посмотрим, почему первая половина ar2 (оставшаяся половина) должна быть выше новой медианы. Это так, потому что, когда мы складываем все элементы вместе, m2 должен быть выше новой медианы (так как m2 ‹m1), что означает, что вся первая половина ar2 также должна быть выше новой медианы. Другими словами, если m - новая медиана двух выбранных половин, m2 ‹m => вся первая половина ar2‹ m. Аналогичный аргумент для нижней половины ar1. Это означает, что новая медиана m останется медианой всего набора.

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

... как они могут сказать, что медиана объединенных массивов будет медианой объединенных массивов, полученных после обрезки половин массивов, то есть медианы массива слияния {1, 12, 15, 26, 38} и { 2, 13, 17, 30, 45} будет медианой массива слияния {2,13,17} и {15, 26, 38}.

Это из-за неравенства, которое вы использовали для обрезки половинок, и из-за определения медианы. Медиана разбивает набор упорядоченных чисел на две половины. Вы знаете, что 15 <= 17 (медиана первого набора меньше или равна медиане второго набора), и поэтому медиана должна находиться между этими двумя значениями. Все, что меньше 15, удаляется, а все, что больше 17, удаляется, потому что они не могут содержать медианное значение (поскольку они не разделяют набор на две половины). Затем вы применяете те же шаги к более узкому набору; после обрезки размер поиска уменьшился вдвое.

Я пытаюсь визуализировать это на этом примере. Соответствующие медианы отмечены *, за исключением базового случая, когда * отмечает числа, используемые для вычисления медианы в этом примере.

1   12   *15*   26    38        2    13   *17*   30  45

          15   *26*   38        2   *13*   17

         *15*   26                   13   *17*           <-- base case

                           16

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

Я предположил, что медиана - это вычисленное число, которое разделяет набор на две половины.
Когда общий набор имеет нечетное количество элементов, медиана - это номер этого набора. Но в случае равномерности иногда вы обнаруживаете, что он рассчитывается так, как я показал в этом примере (но иногда выбирают меньший элемент, если вам нужно убедиться, что медиана берется из набора, и в этом случае это будет 15).

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

    //Median of two sorted arrays
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception {
        int[] A = {1, 3, 11};
        int[] B = {2, 4, 12, 14, 15};
        System.out.println("Ans. "+findMedian(A, B));
        //System.out.println(median(A));
    }

    private static int findMedian(int[] A, int[] B) {
        System.out.println(Arrays.toString(A)+" --- "+ Arrays.toString(B));
        int sA = A.length;
        int sB = B.length;

        if(sA <= 2 && sB <= 2) {
            if(sA <= 1 && sA <= 1) {
                return (A[0]+B[0])/2; 
            } else if(sA <= 1) {
                return (max(A[0], B[0]) + min(A[0], B[1])) / 2;
            } else if(sB <= 1) {
                return (max(A[0], B[0]) + min(A[1], B[0]) ) / 2;
            } else {
                System.out.println("xxx");
                return (max(A[0], B[0]) + min(A[1],B[1])) / 2;
            }
        }

        int mA = median(A);
        int mB = median(B);

        if(mA == mB) {
            return mA;
        } else if(mA < mB) {
            if(sA <= 2) {
                return findMedian(A, Arrays.copyOfRange(B, 0, sB/2+1));     
            } else if(sB <= 2) {
                return findMedian(Arrays.copyOfRange(A, sA/2, sA), B); 
            } else {
                return findMedian(Arrays.copyOfRange(A, sA/2, sA)
                          ,Arrays.copyOfRange(B, 0, sB/2+1)); 
            }
        } else {
            if(sA <= 2) {
                return findMedian(A, Arrays.copyOfRange(B, sB/2, sB));  
            } else if(sB <= 2) {
                return findMedian(Arrays.copyOfRange(A, 0, sA/2+1),B); 
            } else {
                return findMedian(Arrays.copyOfRange(A, 0, sA/2+1)
                          ,Arrays.copyOfRange(B, sB/2, sB)); 
            }
        }
    }

    private static int median(int[] A) {
        int size = A.length;
        if(size == 0 ){
            return 0;
        } else if(size == 1) {
            return A[0];
        }

        if(size%2 == 0 ) {
            return (A[size/2 -1 ] + A[size/2  ])/2;
        }else {
            return A[size/2];
        }
    }

    private static int max(int a, int b) {
        return a > b ? a : b;
    }

    private static int min(int a, int b) {
        return a < b ? a : b;
    }
}

Из-за ограничения равной длины, когда мы сравниваем две медианы, мы можем безопасно отбросить значения.

Если m2 больше, чем m1, мы знаем, что массив 2 должен содержать большее количество больших значений, чем массив 1, и поэтому все маленькие значения ниже m1 не представляют интереса, пока мы отбрасываем равное количество больших значений из массива 2 Результатом будет более короткий массив, но медиана, которую мы ищем, не изменилась, так как мы обрезали одинаково с обеих сторон.

Это как бы напоминает мне нахождение центра масс объекта, поддерживая его руками на большом расстоянии друг от друга, а затем медленно сводя их вместе, удерживая объект в равновесии.

Решение PHP:

function Solve( $aArrayOne, $aArrayTwo )
{
    // Base case
    if( empty( $aArrayOne ) || empty( $aArrayTwo ) )
    {
        return false;
    }
    $iCountOne      = count( $aArrayOne );
    $iCountTwo      = count( $aArrayTwo );

    // Single value arrays base case
    if( $iCountOne === 1 && $iCountOne === $iCountTwo )
    {
        return ( $aArrayOne[ 0 ] + $aArrayTwo[ 0 ] ) / 2;
    }

    $iTotalElements = $iCountOne + $iCountTwo;
    $iHalfElements = floor( $iTotalElements / 2 );
    $aPartial       = [];
    $n              = 0;
    // Append elements to new combined array until midway point
    while( $n <= $iHalfElements )
    {
        // Compared both of the first elements to get the 
        // smallest one into the partial array
        if( $aArrayOne[ 0 ] <= $aArrayTwo[ 0 ] )
        {
            $aPartial[] = array_shift( $aArrayOne );
        }
        else
        {
            $aPartial[] = array_shift( $aArrayTwo );
        }
        ++$n;
    }
    // Check to see if we have an odd or an even array for final element math.
    $bIsOddAndPrecise = $iTotalElements % 2;
    $iMedian = ( $bIsOddAndPrecise ) 
    ? $aPartial[ $n - 1 ] 
    : ( $aPartial[ $n - 1 ] + $aPartial[ $n - 2 ] ) / 2;
    return $iMedian;
}

Проверенные варианты использования:

// $aArrayOne = [1, 3, 4 ];
// $aArrayTwo = [1, 2, 3 ];
// EXPECTED 1,1,2,3,3,4 -> (2+3)/2 2.5
// $aArrayOne = [1, 3, 4, 7, 8, 11, 44, 55, 62];
// $aArrayTwo = [2, 4, 5, 7, 33, 56, 77];
// Expected: 1,2,3,4,4,5,7,7,8,11,33,44,55,56,62,77 -> (7+8)/2 7.5
// $aArrayOne = [1, 3, 4 ];
// $aArrayTwo = [ 100, 100];
// EXPECTED 1,3,4,100,100 -> 4
// $aArrayOne = [1,5,8,10];
// $aArrayTwo = [7,9,14,];
// EXPECTED 1,2,7,8,9,10,14 - > 8
// $aArrayOne = [1,5,8,10];
// $aArrayTwo = [7];
// EXPECTED 1,5,7,8,10 - > 7
// $aArrayOne = [1,5,10];
// $aArrayTwo = [50, 50];
// EXPECTED 1,5,10,50,50 - > 10
// $aArrayOne = [50, 50];
// $aArrayTwo = [1,5,10];
// EXPECTED 1,5,10,50,50 - > 10
// $aArrayOne = [1];
// $aArrayTwo = [1];
// EXPECTED-> 1
// $aArrayOne = [100, 100];
// $aArrayTwo = [100];
// EXPECTED -> 100

Это мое решение на C #:

public double FindMedianSortedArrays (int [] nums1, int [] nums2) {

    List<int> sorted = new List<int>();

    if(nums1.Length>nums2.Length){
        for(int i=0; i<nums1.Length; i++){

            sorted.Add(nums1[i]);

            if(i<nums2.Length)
                sorted.Add(nums2[i]);
        }
    }
    else{
        for(int i=0; i<nums2.Length; i++){

            sorted.Add(nums2[i]);

            if(i<nums1.Length)
                sorted.Add(nums1[i]);
        }
    }

    sorted.Sort();

    if(sorted.Count % 2 !=0)
       return (double)sorted[sorted.Count/2];

       return (double)(sorted[sorted.Count/2-1]+ sorted[sorted.Count/2])/2;
}

Решение Javascript для поиска медианы двух отсортированных массивов:

const findMedian = (arr1, arr2) => {
  const len = arr1.length + arr2.length;
  return len % 2 ? oddMedian(Math.floor(len/2), arr1, arr2) : evenMedian((len/2)-1, len/2, arr1, arr2);
}

const oddMedian = (medianIndex, arr1, arr2) => {
  if (arr1[arr1.length-1] < arr2[0]) {
    if (arr1.length > medianIndex) {
      return arr1[medianIndex];
    } else if (arr1.length <= medianIndex) {
      return arr2[medianIndex - arr1.length];
    }
  } else if (arr2[arr2.length-1] < arr1[0]) {
    if (arr2.length > medianIndex) {
      return arr2[medianIndex];
    } else if (arr2.length <= medianIndex) {
      return arr1[medianIndex - arr2.length];
    }
  } else {
    const [shorterArr, largerArr] = arr1.length < arr2.length ? [arr1, arr2] : [arr2, arr1];
    let j = 0;
    let k = 0;
    const sortedArr = [];
    for (let i = 0; i <= medianIndex; i++) {
      if (shorterArr[j] <= largerArr[k]) {
        sortedArr[i] = shorterArr[j];
        j++;
      } else {
        sortedArr[i] = largerArr[k];
        k++;
      }
    }
    return sortedArr[medianIndex];
  }
}

const evenMedian = (medianIndex1, medianIndex2, arr1, arr2) => {
  if (arr1[arr1.length-1] < arr2[0]) {
    if (arr1.length-1 >= medianIndex2) {
      return (arr1[medianIndex1]+arr1[medianIndex2])/2;
    } else if (arr1.length-1 < medianIndex1) {
      const firstMedianIndex = medianIndex1 - arr1.length;
      return (arr2[firstMedianIndex]+arr2[firstMedianIndex+1])/2;
    } else {
      return (arr1[arr1.length-1] + arr2[0])/2;
    }
  } else if (arr2[arr2.length-1] < arr1[0]) {
    if (arr2.length-1 >= medianIndex2) {
      return (arr2[medianIndex1]+arr2[medianIndex2])/2;
    } else if (arr2.length-1 < medianIndex1) {
      const firstMedianIndex = medianIndex1 - arr2.length;
      return (arr1[firstMedianIndex]+arr1[firstMedianIndex+1])/2;
    } else {
      return (arr2[arr2.length-1] + arr1[0])/2;
    }
  } else {
    const [shorterArr, largerArr] = arr1.length < arr2.length ? [arr1, arr2] : [arr2, arr1];
    let i = 0;
    let j = 0;
    let k = 0;
    const sortedArr = [];
    for (let i = 0; i <= medianIndex2; i++) {
      if (shorterArr[j] <= largerArr[k]) {
        sortedArr.push(shorterArr[j]);
        j++;
      } else {
        sortedArr.push(largerArr[k]);
        k++;
      }
    }
    return (sortedArr[medianIndex1] + sortedArr[medianIndex2])/2;
  }
}

Пример

console.log("Result:", findMedian([1,3,5], [2,4,6,8]));
console.log("Result:", findMedian([1,3,5,7,10], [2,4,6,8]));
console.log("Result:", findMedian([1,3,5,7,10], [2,4,6,8,9]));
console.log("Result:", findMedian([1,3,5], [2,4,6,8,9]));
console.log("Result:", findMedian([1,3,5,7], [2,4,6,8,9,10]));
console.log("Result:", findMedian([1,3,5,7,10], [2,4,6]));
console.log("Result:", findMedian([1,3,5,7], [2,4]));
console.log("Result:", findMedian([1,2,4], [3,5,6,7,8,9,10,11]));
console.log("Result:", findMedian([1], [2, 3, 4]));
console.log("Result:", findMedian([1, 2], [3, 4]));
console.log("Result:", findMedian([1], [2, 3]));

Выход

Result: 4
Result: 5
Result: 5.5
Result: 4.5
Result: 5.5
Result: 4.5
Result: 3.5
Result: 6
Result: 2.5
Result: 2.5
Result: 2

Медиана двух массивов в Java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        double find =0;
        ArrayList list =  new ArrayList();
            for(int i =0;i<n1;i++)
                list.add(nums1[i]);
        
                
            for(int j =0;j<n2;j++)
                list.add(nums2[j]);
        Collections.sort(list);
        
        int n = list.size();
        if(n%2 != 0)
        {
            find = (Integer)list.get(n/2);
            
            
        }
        else if(n%2==0){
            find = (Integer)list.get(n/2-1)+(Integer)list.get(n/2);
            find = find/2;
        }
        return find;
        
    }
}

Решение Swift на 100% работает, протестировано

//Given 2 sorted arrays Ar1 and Ar2 of size N each. Merge the given arrays and 
find the sum of the two middle elements of the merged array.

  func sumOfSortedArray(Ar1:[Int], Ar2:[Int],N:Int)->Int{
      var newArray = [Int]()
      newArray.append(contentsOf: Ar1)
      newArray.append(contentsOf: Ar2)
      newArray = newArray.sorted()
      //this is how we can get middle index by total of both array divided by 2 and need to minus 1 because array always start with 0 not 1.
      let middleElementIndex = ((N+N)/2) - 1
      let sum = newArray[middleElementIndex] + newArray[middleElementIndex + 1]
      print(sum)
      return sum
  }

@jayadev: Я не согласен с вашим ответом.
"Первая половина ar2, все n / 2 элементов должны быть наверху этой новой медианы, а вторая половина arr1 - все n / 2 элементов будет ниже медианы "

Рассмотрим этот тестовый пример: a1 = {1,2,15,16,17} a2 = {4,5,10,18,20}