Find kth largest element from the union of two sorted array - code review - http://articles.leetcode.com/find-k-th-smallest-element-in-union-of

FindKthLargestElementFromUnionOfTwoSortedArray.cs

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

namespace KthLargestElementTwoSortedArrays_OptimalSolution
{
    /*
     * Problem statement:
     * Find kth largest element in the union of two sorted array.
     * 
     * Introduction:
     * 
     * Review Leetcode 4 and Leetcode 215 two algorithm, and then, read the article: 
     * http://articles.leetcode.com/find-k-th-smallest-element-in-union-of
     *   
     *    
     * 
     * Introduction of algorithms for the solutions:
     * There are a few of solutions to solve the problem, one is to merge two sorted array and then
     * find the kth largest element, the solution will take O(m + n) time, where m and n are two arrays's 
     * length respectively. 
     * 
     * But, we do not stop here. Try to beat the solution in time complexity, the following solution
     * use binary search, and then use recursive solution to solve a small subproblem. 
     * 
     * We do not need to sort first k element in the array, and then find kth element. As long as 
     * we know that less than k/2 elements (denoted as m) are smaller than kth element in two sorted 
     * array, then we can solve a small subproblem - find (k - m)th largest element in two sorted 
     * array instead. 
     *        
     * 
     */
    class KthLargestElement
    {
        static void Main(string[] args)
        {
            RunSampleTestcase1();
        }

        /*
         * 5th largest element from a union of two sorted arrays, integers from 1 to 10.          
         */
        public static void RunSampleTestcase1()
        {
            int[] array1 = new int[] { 1, 3, 5, 7, 9 };
            int[] array2 = new int[] { 2, 4, 6, 8, 10 };

            Debug.Assert( FindKthLargestElement(array1, array2, 5) == 5);
        }
        
        public static double FindKthLargestElement(int[] array1, int[] array2, int k)
        {
            return FindKthLargestElement_BinarySearch(array1, array1.Length, array2, array2.Length, k);
        }

        /*
         *
         * Using binary search to find kth largest element from the union of two sorted array 
         * in time complexity O(lg(n + m))
         *
         * Naive solution is to merge two sorted array, and then find kth largest element. 
         * Time complexity is O(n + m), n, m are the length of two arrays respectively. 
         *    
         * Current solution is to use binary search to expedite the search. 
         * 
         * Function spec: 
         *
         * Find kth largest element from two sorted arrays, 
         * @array1 - sorted array ascending order
         * @array2 - soretd array ascending order
         * 
         * Always try to remove k/2 elements one time
         * 
         * Recursive function: subproblem is a smaller problem. 
         */
        private static double FindKthLargestElement_BinarySearch(
            int[] array1,
            int   length1,
            int[] array2,
            int   length2,
            int   k)
        {
            //always assume that length1 is equal or smaller than length2
            if (length1 > length2)
                return FindKthLargestElement_BinarySearch(array2, length2, array1, length1, k);

            if (length1 == 0)
                return array2[k - 1];

            if (k == 1)
                return Math.Min(array1[0], array2[0]);

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

            if (array1[half_k - 1] == array2[rest_kElements - 1])
                return array1[half_k - 1];
            
            if (array1[half_k - 1] < array2[rest_kElements - 1])
            {
                // kth largest element definitely not in the range of array1[i], i is in [0, middleOfSearch_1 - 1]
                int[] newArray1 = ArraySplice(array1, half_k);
                return FindKthLargestElement_BinarySearch(newArray1, length1 - half_k, array2, length2, k - half_k);
            }
            else
            {
                int[] newArray2 = ArraySplice(array2, rest_kElements);
                return FindKthLargestElement_BinarySearch(array1, length1, newArray2, length2 - rest_kElements, k - rest_kElements);
            }
        }

        /*
         * Remove first n items from the array
         * 
         * similar to JavaScript array's API: splice
         * https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/splice
         * 
         * syntax
         * array.splice(start, deleteCount, item1, item2, ...)
         * 
         */
        public static int[] ArraySplice(int[] array, int deleteCount)
        {
            int length = array.Length;

            if (deleteCount <= length)
            {
                int[] result = new int[length - deleteCount];
                for (int i = 0; i < length - deleteCount; i++)
                    result[i] = array[deleteCount + i];

                return result;
            }

            return new int[] { };
        }
    }
}