The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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)