Dados dos arreglos ordenados, a[] y b[], la tarea es encontrar la mediana de estos arreglos ordenados, en complejidad de tiempo O(log n + log m), cuando n es el número de elementos en el primer arreglo, y m es el número de elementos en la segunda array.
Esta es una extensión de la mediana de dos arreglos ordenados de igual tamaño . Aquí también manejamos arrays de tamaño desigual.
Ejemplo:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int Solution(int arr[], int n)
{
// If length of array is even
if (n % 2 == 0)
{
int z = n / 2;
int e = arr[z];
int q = arr[z - 1];
int ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else
{
int z = round(n / 2);
return arr[z];
}
}
// Driver Code
int main() {
// TODO Auto-generated method stub
int arr1[] = { -5, 3, 6, 12, 15 };
int arr2[] = { -12, -10, -6, -3, 4, 10 };
int i = sizeof(arr1) / sizeof(arr1[0]);
int j = sizeof(arr2) / sizeof(arr2[0]);
int arr3[i+j];
int l = i+j;
// Merge two array into one array
for(int k=0;k<i;k++)
{
arr3[k]=arr1[k];
}
int a=0;
for(int k=i;k<l;k++)
{
arr3[k]=arr2[a++];
}
// Sort the merged array
sort(arr3,arr3+l);
// calling the method
cout<<"Median = " << Solution(arr3, l);
}
// This code is contributed by SoumikMondal
Java
// Java program for the above approach
import java.io.*;
import java.util.Arrays;
public class GFG {
public static int Solution(int[] arr)
{
int n = arr.length;
// If length of array is even
if (n % 2 == 0)
{
int z = n / 2;
int e = arr[z];
int q = arr[z - 1];
int ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else
{
int z = Math.round(n / 2);
return arr[z];
}
}
// Driver Code
public static void main(String[] args)
{
// TODO Auto-generated method stub
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
int i = arr1.length;
int j = arr2.length;
int[] arr3 = new int[i + j];
// Merge two array into one array
System.arraycopy(arr1, 0, arr3, 0, i);
System.arraycopy(arr2, 0, arr3, i, j);
// Sort the merged array
Arrays.sort(arr3);
// calling the method
System.out.print("Median = " + Solution(arr3));
}
}
// This code is contributed by Manas Tole
Python3
# Python3 program for the above approach
def Solution(arr):
n = len(arr)
# If length of array is even
if n % 2 == 0:
z = n // 2
e = arr[z]
q = arr[z - 1]
ans = (e + q) / 2
return ans
# If length of array is odd
else:
z = n // 2
ans = arr[z]
return ans
# Driver code
if __name__ == "__main__":
arr1 = [ -5, 3, 6, 12, 15 ]
arr2 = [ -12, -10, -6, -3, 4, 10 ]
# Concatenating the two arrays
arr3 = arr1 + arr2
# Sorting the resultant array
arr3.sort()
print("Median = ", Solution(arr3))
# This code is contributed by kush11
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
public static int Solution(int[] arr)
{
int n = arr.Length;
// If length of array is even
if (n % 2 == 0)
{
int z = n / 2;
int e = arr[z];
int q = arr[z - 1];
int ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else
{
int z = n / 2;
return arr[z];
}
}
// Driver Code
static public void Main (){
// TODO Auto-generated method stub
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
// Merge two array into one array
var myList = new List<int>();
myList.AddRange(arr1);
myList.AddRange(arr2);
int[] arr3 = myList.ToArray();
// Sort the merged array
Array.Sort(arr3);
// calling the method
Console.Write("Median = " + Solution(arr3));
}
}
// This code is contributed by Shubhamsingh10
Javascript
<script>
// Javascript program for the above approach
function Solution(arr, n)
{
// If length of array is even
if (n % 2 == 0)
{
var z = n / 2;
var e = arr[z];
var q = arr[z - 1];
var ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else
{
var z = Math.floor(n / 2);
return arr[z];
}
}
// Driver Code
// TODO Auto-generated method stub
var arr1 = [ -5, 3, 6, 12, 15 ];
var arr2 = [ -12, -10, -6, -3, 4, 10 ];
var i = arr1.length;
var j = arr2.length;
var l = i+j;
// Merge two array into one array
const arr3 = arr1.concat(arr2);
// Sort the merged array
arr3.sort(function(a, b) {
return a - b;
});
// calling the method
document.write("Median = " + Solution(arr3, l));
// This code is contributed by Shubham Singh
</script>
C++
// A Simple Merge based O(n) solution to find
// median of two sorted arrays
#include <bits/stdc++.h>
using namespace std;
/* This function returns median of ar1[] and ar2[].
Assumption in this function:
Both ar1[] and ar2[] are sorted arrays */
int getMedian(int ar1[], int ar2[], int n, int m)
{
int i = 0; /* Current index of input array ar1[] */
int j = 0; /* Current index of input array ar2[] */
int count;
int m1 = -1, m2 = -1;
/*loop till (m+n)/2*/
for (count = 0; count <= (m + n)/2; count++)
{
//store (n+m)/2-1 in m2
m2=m1;
if(i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];
}
else if(i < n)
{
m1 = ar1[i++];
}
// for case when j<m,
else
{
m1 = ar2[j++];
}
}
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
// index is median i.e. (m+n)/2
// other wise median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging ar1 and ar2
if((m + n) % 2 == 1){
return m1;
}
else{
return (m1+m2)/2;
}
}
/* Driver code */
int main()
{
int ar1[] = {900};
int ar2[] = {5,8,10,20};
int n1 = sizeof(ar1)/sizeof(ar1[0]);
int n2 = sizeof(ar2)/sizeof(ar2[0]);
cout << getMedian(ar1, ar2, n1, n2);
}
// This is code is contributed by rathbhupendra, modified by rajesh999
Python
# A Simple Merge based O(n) solution to find # median of two sorted arrays """ This function returns median of ar1[] and ar2[]. Assumption in this function: Both ar1[] and ar2[] are sorted arrays """ def getMedian(ar1, ar2, n, m) : i = 0 # Current index of input array ar1[] j = 0 # Current index of input array ar2[] m1, m2 = -1, -1 for count in range(((n + m) // 2) + 1) : if(i != n and j != m) : if ar1[i] > ar2[j] : m1 = ar2[j] j += 1 else : m1 = ar1[i] i += 1 elif(i < n) : m1 = ar1[i] i += 1 # for case when j<m, else : m1 = ar2[j] j += 1 # return m1 if it's lengt odd else return (m1+m2)//2 return m1 if (n + m) % 2 == 1 else (m1 + m2) // 2 # Driver code ar1 = [900] ar2 = [5, 8, 10, 20] n1 = len(ar1) n2 = len(ar2) print(getMedian(ar1, ar2, n1, n2)) # This code is contributed by divyesh072019
Java
// A Simple Merge based O(n) solution
// to find median of two sorted arrays
class GFG{
// Function to calculate median
static int getMedian(int ar1[], int ar2[],
int n, int m)
{
// Current index of input array ar1[]
int i = 0;
// Current index of input array ar2[]
int j = 0;
int count;
int m1 = -1, m2 = -1;
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
//index is median i.e. (m+n)/2
if ((m + n) % 2 == 1)
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if (i < n)
{
m1 = ar1[i++];
}
// for case when j<m,
else
{
m1 = ar2[j++];
}
}
return m1;
}
// median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging
// ar1 and ar2
else
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
m2 = m1;
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if (i < n)
{
m1 = ar1[i++];
}
// for case when j<m,
else
{
m1 = ar2[j++];
}
}
return (m1 + m2) / 2;
}
}
// Driver code
public static void main(String[] args)
{
int ar1[] = { 900 };
int ar2[] = { 5, 8, 10, 20 };
int n1 = ar1.length;
int n2 = ar2.length;
System.out.println(getMedian(ar1, ar2, n1, n2));
}
}
// This code is contributed by Yash Singhal
Python
# A Simple Merge based O(n) solution to find # median of two sorted arrays """ This function returns median of ar1[] and ar2[]. Assumption in this function: Both ar1[] and ar2[] are sorted arrays """ def getMedian(ar1, ar2, n, m) : i = 0 # Current index of input array ar1[] j = 0 # Current index of input array ar2[] m1, m2 = -1, -1 for count in range(((n + m) // 2) + 1) : if(i != n and j != m) : if ar1[i] > ar2[j] : m1 = ar2[j] j += 1 else : m1 = ar1[i] i += 1 elif(i < n) : m1 = ar1[i] i += 1 # for case when j<m, else : m1 = ar2[j] j += 1 # return m1 if it's length odd else return (m1+m2)//2 return m1 if (n + m) % 2 == 1 else (m1 + m2) // 2 # Driver code ar1 = [900] ar2 = [5, 8, 10, 20] n1 = len(ar1) n2 = len(ar2) print(getMedian(ar1, ar2, n1, n2)) # This code is contributed by divyesh072019
C#
// A Simple Merge based O(n) solution
// to find median of two sorted arrays
using System;
class GFG{
// Function to calculate median
static int getMedian(int []ar1, int []ar2,
int n, int m)
{
// Current index of input array ar1[]
int i = 0;
// Current index of input array ar2[]
int j = 0;
int count;
int m1 = -1, m2 = -1;
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
//index is median i.e. (m+n)/2
if ((m + n) % 2 == 1)
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if (i < n)
{
m1 = ar1[i++];
}
// for case when j<m,
else
{
m1 = ar2[j++];
}
}
return m1;
}
// median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging
// ar1 and ar2
else
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
m2 = m1;
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if (i < n)
{
m1 = ar1[i++];
}
// for case when j<m,
else
{
m1 = ar2[j++];
}
}
return (m1 + m2) / 2;
}
}
// Driver code
public static void Main(String[] args)
{
int []ar1 = { 900 };
int []ar2 = { 5, 8, 10, 20 };
int n1 = ar1.Length;
int n2 = ar2.Length;
Console.WriteLine(getMedian(ar1, ar2, n1, n2));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// A Simple Merge based O(n) solution to find
// median of two sorted arrays
// This function returns median of ar1[] and ar2[].
// Assumption in this function:
// Both ar1[] and ar2[] are sorted arrays
function getMedian(ar1, ar2, n, m)
{
// Current index of input array ar1[]
let i = 0;
// Current index of input array ar2[]
let j = 0;
let count;
let m1 = -1, m2 = -1;
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
// index is median i.e. (m+n)/2
if ((m + n) % 2 == 1)
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if(i < n)
{
m1 = ar1[i++];
}
// For case when j<m,
else
{
m1 = ar2[j++];
}
}
return m1;
}
// Median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging
// ar1 and ar2
else
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
m2 = m1;
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if(i < n)
{
m1 = ar1[i++];
}
// For case when j<m,
else
{
m1 = ar2[j++];
}
}
return (m1 + m2) / 2;
}
}
// Driver code
let ar1 = [900];
let ar2 = [5, 8, 10, 20];
let n1 = ar1.length;
let n2 = ar2.length;
document.write(getMedian(ar1, ar2, n1, n2));
// This code is contributed by divyeshrabadiya07
</script>
C++
// A C++ program to find median of two sorted arrays of
// unequal sizes
#include <bits/stdc++.h>
using namespace std;
// A utility function to find median of two integers
float MO2(int a, int b)
{ return ( a + b ) / 2.0; }
// A utility function to find median of three integers
float MO3(int a, int b, int c)
{
return a + b + c - max(a, max(b, c))
- min(a, min(b, c));
}
// A utility function to find a median of four integers
float MO4(int a, int b, int c, int d)
{
int Max = max( a, max( b, max( c, d ) ) );
int Min = min( a, min( b, min( c, d ) ) );
return ( a + b + c + d - Max - Min ) / 2.0;
}
// Utility function to find median of single array
float medianSingle(int arr[], int n)
{
if (n == 0)
return -1;
if (n%2 == 0)
return (double)(arr[n/2] + arr[n/2-1])/2;
return arr[n/2];
}
// This function assumes that N is smaller than or equal to M
// This function returns -1 if both arrays are empty
float findMedianUtil( int A[], int N, int B[], int M )
{
// If smaller array is empty, return median from second array
if (N == 0)
return medianSingle(B, M);
// If the smaller array has only one element
if (N == 1)
{
// Case 1: If the larger array also has one element,
// simply call MO2()
if (M == 1)
return MO2(A[0], B[0]);
// Case 2: If the larger array has odd number of elements,
// then consider the middle 3 elements of larger array and
// the only element of smaller array. Take few examples
// like following
// A = {9}, B[] = {5, 8, 10, 20, 30} and
// A[] = {1}, B[] = {5, 8, 10, 20, 30}
if (M & 1)
return MO2( B[M/2], MO3(A[0], B[M/2 - 1], B[M/2 + 1]) );
// Case 3: If the larger array has even number of element,
// then median will be one of the following 3 elements
// ... The middle two elements of larger array
// ... The only element of smaller array
return MO3( B[M/2], B[M/2 - 1], A[0] );
}
// If the smaller array has two elements
else if (N == 2)
{
// Case 4: If the larger array also has two elements,
// simply call MO4()
if (M == 2)
return MO4(A[0], A[1], B[0], B[1]);
// Case 5: If the larger array has odd number of elements,
// then median will be one of the following 3 elements
// 1. Middle element of larger array
// 2. Max of first element of smaller array and element
// just before the middle in bigger array
// 3. Min of second element of smaller array and element
// just after the middle in bigger array
if (M & 1)
return MO3 ( B[M/2],
max(A[0], B[M/2 - 1]),
min(A[1], B[M/2 + 1])
);
// Case 6: If the larger array has even number of elements,
// then median will be one of the following 4 elements
// 1) & 2) The middle two elements of larger array
// 3) Max of first element of smaller array and element
// just before the first middle element in bigger array
// 4. Min of second element of smaller array and element
// just after the second middle in bigger array
return MO4 ( B[M/2],
B[M/2 - 1],
max( A[0], B[M/2 - 2] ),
min( A[1], B[M/2 + 1] )
);
}
int idxA = ( N - 1 ) / 2;
int idxB = ( M - 1 ) / 2;
/* if A[idxA] <= B[idxB], then median must exist in
A[idxA....] and B[....idxB] */
if (A[idxA] <= B[idxB] )
return findMedianUtil(A + idxA, N/2 + 1, B, M - idxA );
/* if A[idxA] > B[idxB], then median must exist in
A[...idxA] and B[idxB....] */
return findMedianUtil(A, N/2 + 1, B + idxA, M - idxA );
}
// A wrapper function around findMedianUtil(). This function
// makes sure that smaller array is passed as first argument
// to findMedianUtil
float findMedian( int A[], int N, int B[], int M )
{
if (N > M)
return findMedianUtil( B, M, A, N );
return findMedianUtil( A, N, B, M );
}
// Driver program to test above functions
int main()
{
int A[] = {900};
int B[] = {5, 8, 10, 20};
int N = sizeof(A) / sizeof(A[0]);
int M = sizeof(B) / sizeof(B[0]);
printf("%f", findMedian( A, N, B, M ) );
return 0;
}
Java
// A Java program to find median of two sorted arrays of
// unequal sizes
import java.util.*;
class GFG {
// A utility function to find median of two integers
static float MO2(int a, int b) {
return (float) ((a + b) / 2.0);
}
// A utility function to find median of three integers
static float MO3(int a, int b, int c) {
return a + b + c - Math.max(a, Math.max(b, c)) -
Math.min(a, Math.min(b, c));
}
// A utility function to find a median of four integers
static float MO4(int a, int b, int c, int d) {
int Max = Math.max(a, Math.max(b, Math.max(c, d)));
int Min = Math.min(a, Math.min(b, Math.min(c, d)));
return (float) ((a + b + c + d - Max - Min) / 2.0);
}
// Utility function to find median of single array
static float medianSingle(int arr[], int n) {
if (n == 0)
return -1;
if (n % 2 == 0)
return (float) ((double) (arr[n / 2] +
arr[n / 2 - 1]) / 2);
return arr[n / 2];
}
// This function assumes that N is smaller than or equal to M
// This function returns -1 if both arrays are empty
static float findMedianUtil(int A[], int N, int B[], int M) {
// If smaller array is empty, return median from second array
if (N == 0)
return medianSingle(B, M);
// If the smaller array has only one element
if (N == 1) {
// Case 1: If the larger array also has one element,
// simply call MO2()
if (M == 1)
return MO2(A[0], B[0]);
// Case 2: If the larger array has odd number of elements,
// then consider the middle 3 elements of larger array and
// the only element of smaller array. Take few examples
// like following
// A = {9}, B[] = {5, 8, 10, 20, 30} and
// A[] = {1}, B[] = {5, 8, 10, 20, 30}
if (M % 2 == 1)
return MO2(B[M / 2], (int) MO3(A[0],
B[M / 2 - 1], B[M / 2 + 1]));
// Case 3: If the larger array has even number of element,
// then median will be one of the following 3 elements
// ... The middle two elements of larger array
// ... The only element of smaller array
return MO3(B[M / 2], B[M / 2 - 1], A[0]);
}
// If the smaller array has two elements
else if (N == 2) {
// Case 4: If the larger array also has two elements,
// simply call MO4()
if (M == 2)
return MO4(A[0], A[1], B[0], B[1]);
// Case 5: If the larger array has odd number of elements,
// then median will be one of the following 3 elements
// 1. Middle element of larger array
// 2. Max of first element of smaller array and element
// just before the middle in bigger array
// 3. Min of second element of smaller array and element
// just after the middle in bigger array
if (M % 2 == 1)
return MO3(B[M / 2], Math.max(A[0], B[M / 2 - 1]),
Math.min(A[1], B[M / 2 + 1]));
// Case 6: If the larger array has even number of elements,
// then median will be one of the following 4 elements
// 1) & 2) The middle two elements of larger array
// 3) Max of first element of smaller array and element
// just before the first middle element in bigger array
// 4. Min of second element of smaller array and element
// just after the second middle in bigger array
return MO4(B[M / 2], B[M / 2 - 1],
Math.max(A[0], B[M / 2 - 2]),
Math.min(A[1], B[M / 2 + 1]));
}
int idxA = (N - 1) / 2;
int idxB = (M - 1) / 2;
/*
* if A[idxA] <= B[idxB], then median
must exist in A[idxA....] and B[....idxB]
*/
if (A[idxA] <= B[idxB])
return findMedianUtil(Arrays.copyOfRange(A, idxA, A.length),
N / 2 + 1, B, M - idxA);
/*
* if A[idxA] > B[idxB], then median
must exist in A[...idxA] and B[idxB....]
*/
return findMedianUtil(A, N / 2 + 1,
Arrays.copyOfRange(B, idxB, B.length), M - idxA);
}
// A wrapper function around findMedianUtil(). This function
// makes sure that smaller array is passed as first argument
// to findMedianUtil
static float findMedian(int A[], int N, int B[], int M)
{
if (N > M)
return findMedianUtil(B, M, A, N);
return findMedianUtil(A, N, B, M);
}
// Driver program to test above functions
public static void main(String[] args)
{
int A[] = { 900 };
int B[] = { 5, 8, 10, 20 };
int N = A.length;
int M = B.length;
System.out.printf("%f", findMedian(A, N, B, M));
}
}
// This code is contributed by Princi Singh.
Python3
# A Python3 program to find median of two sorted arrays of
# unequal sizes
# A utility function to find median of two integers
def MO2(a, b) :
return ( a + b ) / 2
# A utility function to find median of three integers
def MO3(a, b, c) :
return a + b + c - max(a, max(b, c)) - min(a, min(b, c))
# A utility function to find a median of four integers
def MO4(a, b, c, d) :
Max = max( a, max( b, max( c, d ) ) )
Min = min( a, min( b, min( c, d ) ) )
return ( a + b + c + d - Max - Min ) / 2
# Utility function to find median of single array
def medianSingle(arr, n) :
if (n == 0) :
return -1
if (n % 2 == 0) :
return (arr[n / 2] + arr[n / 2 - 1]) / 2
return arr[n / 2]
# This function assumes that N is smaller than or equal to M
# This function returns -1 if both arrays are empty
def findMedianUtil(A, N, B, M) :
# If smaller array is empty, return median from second array
if (N == 0) :
return medianSingle(B, M)
# If the smaller array has only one element
if (N == 1) :
# Case 1: If the larger array also has one element,
# simply call MO2()
if (M == 1) :
return MO2(A[0], B[0])
# Case 2: If the larger array has odd number of elements,
# then consider the middle 3 elements of larger array and
# the only element of smaller array. Take few examples
# like following
# A = {9}, B[] = {5, 8, 10, 20, 30} and
# A[] = {1}, B[] = {5, 8, 10, 20, 30}
if (M & 1 != 0) :
return MO2( B[M / 2], MO3(A[0], B[M / 2 - 1], B[M / 2 + 1]) )
# Case 3: If the larger array has even number of element,
# then median will be one of the following 3 elements
# ... The middle two elements of larger array
# ... The only element of smaller array
return MO3(B[M // 2], B[M // 2 - 1], A[0])
# If the smaller array has two elements
elif (N == 2) :
# Case 4: If the larger array also has two elements,
# simply call MO4()
if (M == 2) :
return MO4(A[0], A[1], B[0], B[1])
# Case 5: If the larger array has odd number of elements,
# then median will be one of the following 3 elements
# 1. Middle element of larger array
# 2. Max of first element of smaller array and element
# just before the middle in bigger array
# 3. Min of second element of smaller array and element
# just after the middle in bigger array
if (M & 1 != 0) :
return MO3 (B[M / 2], max(A[0], B[M / 2 - 1]), min(A[1], B[M / 2 + 1]))
# Case 6: If the larger array has even number of elements,
# then median will be one of the following 4 elements
# 1) & 2) The middle two elements of larger array
# 3) Max of first element of smaller array and element
# just before the first middle element in bigger array
# 4. Min of second element of smaller array and element
# just after the second middle in bigger array
return MO4 (B[M / 2], B[M / 2 - 1], max( A[0], B[M / 2 - 2] ), min( A[1], B[M / 2 + 1] ))
idxA = ( N - 1 ) / 2
idxB = ( M - 1 ) / 2
''' if A[idxA] <= B[idxB], then median must exist in
A[idxA....] and B[....idxB] '''
if (A[idxA] <= B[idxB] ) :
return findMedianUtil(A + idxA, N / 2 + 1, B, M - idxA )
''' if A[idxA] > B[idxB], then median must exist in
A[...idxA] and B[idxB....] '''
return findMedianUtil(A, N / 2 + 1, B + idxA, M - idxA )
# A wrapper function around findMedianUtil(). This function
# makes sure that smaller array is passed as first argument
# to findMedianUtil
def findMedian(A, N, B, M) :
if (N > M) :
return findMedianUtil( B, M, A, N );
return findMedianUtil( A, N, B, M )
# Driver code
A = [900]
B = [5, 8, 10, 20]
N = len(A)
M = len(B)
print(findMedian(A, N, B, M ))
# This code is contributed by divyesh072019
C#
// A C# program to find median of two sorted arrays of
// unequal sizes
using System;
class GFG
{
// A utility function to find median of two integers
static float MO2(int a, int b)
{
return (float) ((a + b) / 2.0);
}
// A utility function to find median of three integers
static float MO3(int a, int b, int c)
{
return a + b + c - Math.Max(a, Math.Max(b, c)) -
Math.Min(a, Math.Min(b, c));
}
// A utility function to find a median of four integers
static float MO4(int a, int b, int c, int d)
{
int Max = Math.Max(a, Math.Max(b, Math.Max(c, d)));
int Min = Math.Min(a, Math.Min(b, Math.Min(c, d)));
return (float) ((a + b + c + d - Max - Min) / 2.0);
}
// Utility function to find median of single array
static float medianSingle(int[] arr, int n)
{
if (n == 0)
return -1;
if (n % 2 == 0)
return (float) ((double) (arr[n / 2] +
arr[n / 2 - 1]) / 2);
return arr[n / 2];
}
static int[] copyOfRange (int[] src, int start, int end)
{
int len = end - start;
int[] dest = new int[len];
Array.Copy(src, start, dest, 0, len);
return dest;
}
// This function assumes that N is smaller than or equal to M
// This function returns -1 if both arrays are empty
static float findMedianUtil(int[] A, int N,
int[] B, int M)
{
// If smaller array is empty,
// return median from second array
if (N == 0)
return medianSingle(B, M);
// If the smaller array has only one element
if (N == 1)
{
// Case 1: If the larger array also has one element,
// simply call MO2()
if (M == 1)
return MO2(A[0], B[0]);
// Case 2: If the larger array has odd number of elements,
// then consider the middle 3 elements of larger array and
// the only element of smaller array. Take few examples
// like following
// A = {9}, B[] = {5, 8, 10, 20, 30} and
// A[] = {1}, B[] = {5, 8, 10, 20, 30}
if (M % 2 == 1)
return MO2(B[M / 2], (int) MO3(A[0],
B[M / 2 - 1], B[M / 2 + 1]));
// Case 3: If the larger array has even number of element,
// then median will be one of the following 3 elements
// ... The middle two elements of larger array
// ... The only element of smaller array
return MO3(B[M / 2], B[M / 2 - 1], A[0]);
}
// If the smaller array has two elements
else if (N == 2)
{
// Case 4: If the larger array also has two elements,
// simply call MO4()
if (M == 2)
return MO4(A[0], A[1], B[0], B[1]);
// Case 5: If the larger array has odd number of elements,
// then median will be one of the following 3 elements
// 1. Middle element of larger array
// 2. Max of first element of smaller array and element
// just before the middle in bigger array
// 3. Min of second element of smaller array and element
// just after the middle in bigger array
if (M % 2 == 1)
return MO3(B[M / 2], Math.Max(A[0], B[M / 2 - 1]),
Math.Min(A[1], B[M / 2 + 1]));
// Case 6: If the larger array has even number of elements,
// then median will be one of the following 4 elements
// 1) & 2) The middle two elements of larger array
// 3) Max of first element of smaller array and element
// just before the first middle element in bigger array
// 4. Min of second element of smaller array and element
// just after the second middle in bigger array
return MO4(B[M / 2], B[M / 2 - 1],
Math.Max(A[0], B[M / 2 - 2]),
Math.Min(A[1], B[M / 2 + 1]));
}
int idxA = (N - 1) / 2;
int idxB = (M - 1) / 2;
/*
* if A[idxA] <= B[idxB], then median
must exist in A[idxA....] and B[....idxB]
*/
if (A[idxA] <= B[idxB])
return findMedianUtil(copyOfRange(A, idxA, A.Length),
N / 2 + 1, B, M - idxA);
/*
* if A[idxA] > B[idxB], then median
must exist in A[...idxA] and B[idxB....]
*/
return findMedianUtil(A, N / 2 + 1,
copyOfRange(B, idxB, B.Length), M - idxA);
}
// A wrapper function around findMedianUtil(). This function
// makes sure that smaller array is passed as first argument
// to findMedianUtil
static float findMedian(int[] A, int N, int[] B, int M)
{
if (N > M)
return findMedianUtil(B, M, A, N);
return findMedianUtil(A, N, B, M);
}
// Driver code
static void Main()
{
int[] A = { 900 };
int[] B = { 5, 8, 10, 20 };
int N = A.Length;
int M = B.Length;
Console.WriteLine(findMedian(A, N, B, M));
}
}
// This code is contributed by divyeshrabadiya07
PHP
<?php
// A PHP program to find median
// of two sorted arrays of
// unequal sizes
// A utility function to
// find median of two integers
function MO2($a, $b)
{
return ($a + $b) / 2.0;
}
// A utility function to
// find median of three integers
function MO3($a, $b, $c)
{
return $a + $b + $c -
max($a, max($b, $c)) -
min($a, min($b, $c));
}
// A utility function to find
// median of four integers
function MO4($a, $b, $c, $d)
{
$Max = max($a, max($b, max($c, $d)));
$Min = min($a, min($b, min( $c, $d)));
return ($a + $b + $c + $d - $Max - $Min) / 2.0;
}
// Utility function to
// find median of single array
function medianSingle($arr, $n)
{
if ($n == 0)
return -1;
if ($n % 2 == 0)
return ($arr[$n / 2] +
$arr[$n / 2 - 1]) / 2;
return $arr[$n / 2];
}
// This function assumes that N
// is smaller than or equal to M
// This function returns -1 if
// both arrays are empty
function findMedianUtil(&$A, $N, &$B, $M )
{
// If smaller array is empty,
// return median from second array
if ($N == 0)
return medianSingle($B, $M);
// If the smaller array
// has only one element
if ($N == 1)
{
// Case 1: If the larger
// array also has one
// element, simply call MO2()
if ($M == 1)
return MO2($A[0], $B[0]);
// Case 2: If the larger array
// has odd number of elements,
// then consider the middle 3
// elements of larger array and
// the only element of smaller
// array. Take few examples
// like following
// $A = array(9),
// $B = array(5, 8, 10, 20, 30)
// and $A = array(1),
// $B = array(5, 8, 10, 20, 30)
if ($M & 1)
return MO2($B[$M / 2], $MO3($A[0],
$B[$M / 2 - 1],
$B[$M / 2 + 1]));
// Case 3: If the larger array
// has even number of element,
// then median will be one of
// the following 3 elements
// ... The middle two elements
// of larger array
// ... The only element of
// smaller array
return MO3($B[$M / 2],
$B[$M / 2 - 1], $A[0]);
}
// If the smaller array
// has two elements
else if ($N == 2)
{
// Case 4: If the larger
// array also has two elements,
// simply call MO4()
if ($M == 2)
return MO4($A[0], $A[1],
$B[0], $B[1]);
// Case 5: If the larger array
// has odd number of elements,
// then median will be one of
// the following 3 elements
// 1. Middle element of
// larger array
// 2. Max of first element of
// smaller array and element
// just before the middle
// in bigger array
// 3. Min of second element
// of smaller array and element
// just after the middle
// in bigger array
if ($M & 1)
return MO3 ($B[$M / 2],
max($A[0], $B[$M / 2 - 1]),
min($A[1], $B[$M / 2 + 1]));
// Case 6: If the larger array
// has even number of elements,
// then median will be one of
// the following 4 elements
// 1) & 2) The middle two
// elements of larger array
// 3) Max of first element of
// smaller array and element
// just before the first middle
// element in bigger array
// 4. Min of second element of
// smaller array and element
// just after the second
// middle in bigger array
return MO4 ($B[$M / 2],
$B[$M / 2 - 1],
max($A[0], $B[$M / 2 - 2]),
min($A[1], $B[$M / 2 + 1]));
}
$idxA = ($N - 1 ) / 2;
$idxB = ($M - 1 ) / 2;
/* if $A[$idxA] <= $B[$idxB], then
median must exist in
$A[$idxA....] and $B[....$idxB] */
if ($A[$idxA] <= $B[$idxB] )
return findMedianUtil($A + $idxA,
$N / 2 + 1, $B,
$M - $idxA );
/* if $A[$idxA] > $B[$idxB],
then median must exist in
$A[...$idxA] and $B[$idxB....] */
return findMedianUtil($A, $N/2 + 1,
$B + $idxA, $M - $idxA );
}
// A wrapper function around
// findMedianUtil(). This
// function makes sure that
// smaller array is passed as
// first argument to findMedianUtil
function findMedian(&$A, $N,
&$B, $M )
{
if ($N > $M)
return findMedianUtil($B, $M,
$A, $N );
return findMedianUtil($A, $N,
$B, $M );
}
// Driver Code
$A = array(900);
$B = array(5, 8, 10, 20);
$N = sizeof($A);
$M = sizeof($B);
echo findMedian( $A, $N, $B, $M );
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// A Javascript program to find median of two sorted arrays of
// unequal sizes
// A utility function to find median of two integers
function MO2(a,b)
{
return ((a + b) / 2.0);
}
// A utility function to find median of three integers
function MO3(a, b, c)
{
return a + b + c - Math.max(a, Math.max(b, c)) -
Math.min(a, Math.min(b, c));
}
// A utility function to find a median of four integers
function MO4(a, b, c, d)
{
let Max = Math.max(a, Math.max(b, Math.max(c, d)));
let Min = Math.min(a, Math.min(b, Math.min(c, d)));
return ((a + b + c + d - Max - Min) / 2.0);
}
// Utility function to find median of single array
function medianSingle(arr, n)
{
if (n == 0)
return -1;
if (n % 2 == 0)
return ( (arr[n / 2] +
arr[n / 2 - 1]) / 2);
return arr[n / 2];
}
// This function assumes that N is smaller than or equal to M
// This function returns -1 if both arrays are empty
function findMedianUtil(A, N, B, M)
{
// If smaller array is empty, return median from second array
if (N == 0)
return medianSingle(B, M);
// If the smaller array has only one element
if (N == 1) {
// Case 1: If the larger array also has one element,
// simply call MO2()
if (M == 1)
return MO2(A[0], B[0]);
// Case 2: If the larger array has odd number of elements,
// then consider the middle 3 elements of larger array and
// the only element of smaller array. Take few examples
// like following
// A = {9}, B[] = {5, 8, 10, 20, 30} and
// A[] = {1}, B[] = {5, 8, 10, 20, 30}
if (M % 2 == 1)
return MO2(B[M / 2], MO3(A[0],
B[M / 2 - 1], B[M / 2 + 1]));
// Case 3: If the larger array has even number of element,
// then median will be one of the following 3 elements
// ... The middle two elements of larger array
// ... The only element of smaller array
return MO3(B[M / 2], B[M / 2 - 1], A[0]);
}
// If the smaller array has two elements
else if (N == 2) {
// Case 4: If the larger array also has two elements,
// simply call MO4()
if (M == 2)
return MO4(A[0], A[1], B[0], B[1]);
// Case 5: If the larger array has odd number of elements,
// then median will be one of the following 3 elements
// 1. Middle element of larger array
// 2. Max of first element of smaller array and element
// just before the middle in bigger array
// 3. Min of second element of smaller array and element
// just after the middle in bigger array
if (M % 2 == 1)
return MO3(B[M / 2], Math.max(A[0], B[M / 2 - 1]),
Math.min(A[1], B[M / 2 + 1]));
// Case 6: If the larger array has even number of elements,
// then median will be one of the following 4 elements
// 1) & 2) The middle two elements of larger array
// 3) Max of first element of smaller array and element
// just before the first middle element in bigger array
// 4. Min of second element of smaller array and element
// just after the second middle in bigger array
return MO4(B[M / 2], B[M / 2 - 1],
Math.max(A[0], B[M / 2 - 2]),
Math.min(A[1], B[M / 2 + 1]));
}
let idxA = (N - 1) / 2;
let idxB = (M - 1) / 2;
/*
* if A[idxA] <= B[idxB], then median
must exist in A[idxA....] and B[....idxB]
*/
if (A[idxA] <= B[idxB])
return findMedianUtil(A.slice(idxA, A.length),
N / 2 + 1, B, M - idxA);
/*
* if A[idxA] > B[idxB], then median
must exist in A[...idxA] and B[idxB....]
*/
return findMedianUtil(A, N / 2 + 1,
B.slice( idxB, B.length), M - idxA);
}
// A wrapper function around findMedianUtil(). This function
// makes sure that smaller array is passed as first argument
// to findMedianUtil
function findMedian(A,N,B,M)
{
if (N > M)
return findMedianUtil(B, M, A, N);
return findMedianUtil(A, N, B, M);
}
// Driver program to test above functions
let A = [ 900];
let B = [5, 8, 10, 20];
let N = A.length;
let M = B.length;
document.write(findMedian(A, N, B, M));
// This code is contributed by avanitrachhadiya2155
</script>
C++
#include <bits/stdc++.h>
using namespace std;
// Method to find median
double Median(vector<int>& A, vector<int>& B)
{
int n = A.size();
int m = B.size();
if (n > m)
return Median(B, A); // Swapping to make A smaller
int start = 0;
int end = n;
int realmidinmergedarray = (n + m + 1) / 2;
while (start <= end) {
int mid = (start + end) / 2;
int leftAsize = mid;
int leftBsize = realmidinmergedarray - mid;
int leftA
= (leftAsize > 0)
? A[leftAsize - 1]
: INT_MIN; // checking overflow of indices
int leftB
= (leftBsize > 0) ? B[leftBsize - 1] : INT_MIN;
int rightA
= (leftAsize < n) ? A[leftAsize] : INT_MAX;
int rightB
= (leftBsize < m) ? B[leftBsize] : INT_MAX;
// if correct partition is done
if (leftA <= rightB and leftB <= rightA) {
if ((m + n) % 2 == 0)
return (max(leftA, leftB)
+ min(rightA, rightB))
/ 2.0;
return max(leftA, leftB);
}
else if (leftA > rightB) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
// Driver code
int main()
{
vector<int> arr1 = { -5, 3, 6, 12, 15 };
vector<int> arr2 = { -12, -10, -6, -3, 4, 10 };
cout << "Median of the two arrays are" << endl;
cout << Median(arr1, arr2);
return 0;
}
Java
public class GFG {
// Method to find median
static double Median(int[] A, int[] B)
{
int n = A.length;
int m = B.length;
if (n > m)
return Median(B, A); // Swapping to make A smaller
int start = 0;
int end = n;
int realmidinmergedarray = (n + m + 1) / 2;
while (start <= end) {
int mid = (start + end) / 2;
int leftAsize = mid;
int leftBsize = realmidinmergedarray - mid;
int leftA
= (leftAsize > 0)
? A[leftAsize - 1]
: Integer.MIN_VALUE; // checking overflow of indices
int leftB
= (leftBsize > 0) ? B[leftBsize - 1] : Integer.MIN_VALUE;
int rightA
= (leftAsize < n) ? A[leftAsize] : Integer.MAX_VALUE;
int rightB
= (leftBsize < m) ? B[leftBsize] : Integer.MAX_VALUE;
// if correct partition is done
if (leftA <= rightB && leftB <= rightA) {
if ((m + n) % 2 == 0)
return (Math.max(leftA, leftB)
+ Math.min(rightA, rightB))
/ 2.0;
return Math.max(leftA, leftB);
}
else if (leftA > rightB) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
// Driver code
public static void main(String[] args) {
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
System.out.println("Median of the two arrays are");
System.out.println(Median(arr1, arr2));
}
}
// This code is contributed by Hritik
Python3
class Solution:
# Method to find median
def Median(self, A, B):
# Assumption both A and B cannot be empty
n = len(A)
m = len(B)
if (n > m):
return self.Median(B, A) # Swapping to make A smaller
start = 0
end = n
realmidinmergedarray = (n + m + 1) // 2
while (start <= end):
mid = (start + end) // 2
leftAsize = mid
leftBsize = realmidinmergedarray - mid
# checking overflow of indices
leftA = A[leftAsize - 1] if (leftAsize > 0) else float('-inf')
leftB = B[leftBsize - 1] if (leftBsize > 0) else float('-inf')
rightA = A[leftAsize] if (leftAsize < n) else float('inf')
rightB = B[leftBsize] if (leftBsize < m) else float('inf')
# if correct partition is done
if leftA <= rightB and leftB <= rightA:
if ((m + n) % 2 == 0):
return (max(leftA, leftB) + min(rightA, rightB)) / 2.0
return max(leftA, leftB)
elif (leftA > rightB):
end = mid - 1
else:
start = mid + 1
# Driver code
ans = Solution()
arr1 = [-5, 3, 6, 12, 15]
arr2 = [-12, -10, -6, -3, 4, 10]
print("Median of the two arrays is {}".format(ans.Median(arr1, arr2)))
# This code is contributed by Arpan
C#
using System;
public class GFG {
// Method to find median
static double Median(int[] A, int[] B)
{
int n = A.Length;
int m = B.Length;
if (n > m)
return Median(B, A); // Swapping to make A smaller
int start = 0;
int end = n;
int realmidinmergedarray = (n + m + 1) / 2;
while (start <= end) {
int mid = (start + end) / 2;
int leftAsize = mid;
int leftBsize = realmidinmergedarray - mid;
int leftA
= (leftAsize > 0)
? A[leftAsize - 1]
: Int32.MinValue; // checking overflow of indices
int leftB
= (leftBsize > 0) ? B[leftBsize - 1] : Int32.MinValue;
int rightA
= (leftAsize < n) ? A[leftAsize] : Int32.MaxValue;
int rightB
= (leftBsize < m) ? B[leftBsize] : Int32.MaxValue;
// if correct partition is done
if (leftA <= rightB && leftB <= rightA) {
if ((m + n) % 2 == 0)
return (Math.Max(leftA, leftB)
+ Math.Min(rightA, rightB))
/ 2.0;
return Math.Max(leftA, leftB);
}
else if (leftA > rightB) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
// Driver code
public static void Main() {
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
Console.WriteLine("Median of the two arrays are");
Console.WriteLine(Median(arr1, arr2));
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Method to find median
function Median(A, B) {
let n = A.length;
let m = B.length;
if (n > m)
return Median(B, A); // Swapping to make A smaller
let start = 0;
let end = n;
let realmidinmergedarray = Math.floor((n + m + 1) / 2);
while (start <= end) {
let mid = Math.floor((start + end) / 2);
let leftAsize = mid;
let leftBsize = realmidinmergedarray - mid;
let leftA
= (leftAsize > 0)
? A[leftAsize - 1]
: Number.MIN_VALUE; // checking overflow of indices
let leftB
= (leftBsize > 0) ? B[leftBsize - 1] : INT_MIN;
let rightA
= (leftAsize < n) ? A[leftAsize] : INT_MAX;
let rightB
= (leftBsize < m) ? B[leftBsize] : INT_MAX;
// if correct partition is done
if (leftA <= rightB && leftB <= rightA) {
if ((m + n) % 2 == 0)
return Math.floor((Math.max(leftA, leftB)
+ Math.min(rightA, rightB))
/ 2.0);
return Math.max(leftA, leftB);
}
else if (leftA > rightB) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
// Driver code
let arr1 = [-5, 3, 6, 12, 15];
let arr2 = [-12, -10, -6, -3, 4, 10];
document.write("Median of the two arrays are" + "<br>");
document.write(Median(arr1, arr2))
// This code is contributed by Potta Lokesh
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA