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

# Algorithms

## 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.