Arrays & Strings

Problem 
Find the median of two sorted arrays.
Consider an array { 1, 3, 17, 26, 38 } [ Odd no. of elements ]
Median = arr[n/2] = arr[5/2] = arr[2] = 17
For an array with even no. of elements,
Median = ( ( arr[n/2] + arr[n/2 + 1] ) / 2 )
For e.g, Median for the array { 1, 3, 17, 23, 26, 38 } is (17 + 23) / 2 = 20
Given two sorted arrays, find the median of the resultant array formed after merging.

Solution 
We can simple merge the two sorted arrays and then find median of the resultant algorithm.
But we will go for a better and more efficient approach.
Let’s explain the approach with an example :-
Consider the arrays arr1 = { 1, 3, 17, 26, 38 } and arr2 = { 2, 7, 8, 30, 46 }
1st Iteration :: Median of arr1 = 17 & Median of arr2 = 8
Since median(arr1) > median(arr2), so we can conclude that median would be in 1st half of arr1 &
2nd half of arr2.
Thus we need to consider { 1, 3, 17 } of arr1 and { 8, 30, 46 } of arr2.
2nd Iteration :: Median would be in { 3, 17 } of arr1 & { 8, 30 } of arr2.
3rd Iteration :: We get the final median = (17 + 8) / 2 = 12 [boundary condition]
Boundary conditions :-
Median for 2 sorted arrays of size 2 :-
Consider arr1 = { 3, 17 } and arr2 = { 8, 30 } .
Median = ( max(arr1[0], arr2[0]) + min(arr1[1], arr2[1]) ) / 2 = ( max(3,8) + min(17,30) ) / 2 = ( 8 + 17 ) / 2 = 12.
Median for 2 sorted arrays of size 1 :-
Consider arr1 = { 5 } & { 3 }.
Median = ( arr1[0] + arr2[0] ) / 2 = ( 5 + 3 ) / 2 = 4.

#include<iostream>
using namespace std;

int max(int a, int b) {
   return ((a > b) ? a : b);
}
int min(int a, int b) {
   return ((a < b) ? a : b);
}

// get median of an array
int median(int arr[], int size) {
   if (size % 2 == 0)
         return (arr[size/2] + arr[size/2-1])/2;
   else
         return arr[size/2];
}

// get the median of two sorted arrays
int medianSortedArrays(int arr1[], int arr2[], int size) {
   int med1;
   int med2;

   if(size <= 0) return -1;
   if(size == 1) return (arr1[0] + arr2[0])/2;
   if (size == 2) return (max(arr1[0], arr2[0]) + min(arr1[1], arr2[1])) / 2;

   med1 = median(arr1, size); // median of the first array
   med2 = median(arr2, size); // median of the second array 

   // we can return either med1 or med2
   if(med1 == med2) return med1;

   if (med1 < med2) {
      // median lies in 2nd half of 1st array and 1st half of 2nd array
      return medianSortedArrays(arr1 + size/2, arr2, size - size/2);
   }
   else {
      // median lies in 1st half of 1st array and 2nd half of 2nd array
      return medianSortedArrays(arr2 + size/2, arr1, size - size/2);
   }
}

// main
int main() {
   int arr1[] = {1, 3, 17, 26, 38};
   int arr2[] = {2, 7, 8, 30, 46};
   //1,2,3,7,8,17,26,38,46
   //1,3,17    8,30,46
   //3,17   8,30
   //(17+8)/2
   cout<<"\nMedian of the 2 sorted arrays is "<<medianSortedArrays(arr1, arr2, 5);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j – i ) s.t arr(j) > arr(i)
About    Contact    Sitemap    Terms    Privacy