Leetcode discuss: 4. Median of Two Sorted Arrays

Here is the link. 

C# | June 15, 2020 | median is special case: kth largest/ smallest

June 15, 2020
Problem statement:
Find median of two sorted arrays.

It is my favorite algorithm to review and practice, kth largest algorithm and binary search algorithm both are important ones to review. Median is the special case of kth element, so the more generic question is to find kth largest smallest element in two sorted arrays. .

My practice was done in 2018. This is my second practice, I did in 2020.

Here are my practice on June 15 2020:

1. Find kth smallest element is easy to write compared to kth largest one;
2. Convert median algorithm to find** kth smallest element** in two sorted arrays;
3. To avoid copy of the array, add an argument: start index of the array in design of function FindKthSmallestElementBinarySearch;
4. Use C# Tuple class to cut down function arguments to three; And also combine two arguments for one array together. <- this may cause array copy - Do not do it. July 6 2022
5. Be super cautious - length of array to work on is shortened since start position is specified, not starting from 0;
6. Binary search is interesting, compare two position's value in two arrays and then determine which one to remove half of k elements.
7. Go back to review my first practice written in 2018, and my review with more detail about the algorithm.

Time complexity
O(logN), N is the sum of the two arrays' length.
It is important to check - No copy of the array since it will take O(N) time to make a copy of the array.
Instead always work on the same array, but specify the start index position of the array.

July 5, 2022 | two down votes | What to improve?
I came back to review the discuss post, and I like to find a list of things to work on to make improvements.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_4_median_of_two_sorted_arrays
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = FindMedianSortedArrays(new int[] { 1, 2 }, new int[] { 3, 4 });
            Debug.Assert(Math.Abs(result - 2.5) < 0.001);
        }

        /// <summary>
        /// code review on June 15, 2020
        /// 
        /// </summary>
        /// <param name="A"></param>
        /// <param name="B"></param>
        /// <returns></returns>
        public static double FindMedianSortedArrays(int[] A, int[] B)
        {
            var lengthA = A.Length;
            var lengthB = B.Length;

            bool isEven = (lengthB + lengthA) % 2 == 0;
            var firstIndex = 0;
            var lastIndex = lengthB + lengthA - 1;
            var middle = firstIndex + (lastIndex - firstIndex) / 2;
            int middlePlusOne = middle + 1;

            // one array is empty
            if (lengthA == 0)
            {
                return (!isEven) ? B[middle] : (B[middle] + B[middlePlusOne]) / 2.0;
            }

            if (lengthB == 0)
            {
                return (!isEven) ? A[middle] : (A[middle] + A[middlePlusOne]) / 2.0;
            }

            // Find two values if total number of elements is even 
            if (isEven)
            {
                var middleValue = FindKthLargestElement(A, B, getKthLargest(middle, lastIndex));
                var middlePlusOneValue = FindKthLargestElement(A, B, getKthLargest(middlePlusOne, lastIndex));

                return (middleValue + middlePlusOneValue) / 2.0;
            }
            else
            {
                return FindKthLargestElement(A, B, getKthLargest(middle, lastIndex));
            }
        }

        /// <summary>
        /// assuming the array is in ascending order
        /// </summary>
        /// <param name="index"></param>
        /// <param name="lastIndex"></param>
        /// <returns></returns>
        private static int getKthLargest(int index, int lastIndex)
        {
            return lastIndex - index + 1;
        }

        /// <summary>
        /// code review on June 15, 2020
        /// convert kth largest problem to kth smallest problem, so we can apply binary search from smallest one instead
        /// </summary>
        /// <param name="array1"></param>
        /// <param name="array2"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static double FindKthLargestElement(int[] array1, int[] array2, int k)
        {
            int length1 = array1.Length;
            int length2 = array2.Length;
            int newK = length1 + length2 - k + 1;  // bug in code review, need to add 1 here

            return FindKthSmallestElementBinarySearch(array1, 0, array2, 0, newK);
        }

        /// <summary>
        /// code review on June 15, 2020         
        /// Use Tuple<int[], int>
        /// array, start and end index
        /// </summary>       
        private static double FindKthSmallestElementBinarySearch(
           int[] array1, int start1,
           int[] array2, int start2,
           int k)
        {
            //always assume that length1 is equal or smaller than length2         
            // rest of array
            var length1 = array1.Length - start1;
            var length2 = array2.Length - start2;

            if (length1 > length2)
            {
                return FindKthSmallestElementBinarySearch(array2, start2, array1, start1, k);
            }

            if (length1 == 0)
            {
                return array2[start2 + k - 1];
            }

            if (k == 1)
            {
                return Math.Min(array1[start1], array2[start2]);
            }

            //divide k into two parts  
            int halfK = Math.Min(k / 2, length1);
            int rest = k - halfK;

            int middle1 = start1 + halfK - 1;
            int middle2 = start2 + rest - 1;
            var middleValue1 = array1[middle1];
            var middleValue2 = array2[middle2];

            if (middleValue1 == middleValue2)
            {
                return array1[middle1];
            }

            // remove halfK in the first array 
            if (middleValue1 < middleValue2)
            {
                // Go to solve a smaller subproblem, remove first part of the array1
                int next1 = start1 + halfK;
                int smallerK = k - halfK;

                return FindKthSmallestElementBinarySearch(
                    array1, next1,
                    array2, start2,
                    smallerK);
            }
            else   // remove rest
            {
                // Go to solve a smaller subproblem, remove first part of the array2
                int next2 = start2 + rest;
                int smallerK = k - rest;

                return FindKthSmallestElementBinarySearch(
                    array1, start1,
                    array2, next2,
                    smallerK);
            }
        }
    }
}