Find kth largest element in union of two sorted arrays - after code review - http://codereview.stackexchange.com/questions/152028/find-kth-largest-element-in-the-union-of-two-sorted-array

FindKthLargestElementInUnionTwoSortedArrays.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.          
         * 10, 9, 8, 7, 6, so 6 is the 5th largest element 
         */
        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) == 6);
        }

        public static double FindKthLargestElement(int[] array1, int[] array2, int k)
        {
            int length1 = array1.Length; 
            int length2 = array2.Length;
            int nthSmallest = length1 + length2 - k; 

            return FindKthSmallestElement_BinarySearch(array1, 0, array1.Length, array2, 0, array2.Length, nthSmallest);
        }

        /*
         *
         * Using binary search to find kth smallest 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 smallest element from two sorted arrays in ascending order, 
         * @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. 
         * 
         * Warning: do not do the array copy - it takes O(N) time, more time complexity than binary search O(logN)
         *  otherwise, the alogorithm time complexity will go up to O(N). 
         *  
         * Detail see the code review 
         * http://codereview.stackexchange.com/questions/152028/find-kth-largest-element-in-the-union-of-two-sorted-array
         * comment from JS1
         * Just so you know, your solution appears to be O(log⁡k∗(n+m)). The reason is that ArraySplice() makes 
         * a copy of the array, which takes either O(n)O(n) or O(m)O(m) time. If you would just avoid doing 
         * the copy and instead pass a starting index for each array to your function, you would be down to 
         * O(logk)O(log⁡k) time. – JS1 Jan 9
         */
        private static double FindKthSmallestElement_BinarySearch(
           int[] array1,
           int   start1, 
           int   length1,
           int[] array2,
           int   start2, 
           int   length2,
           int   k)
        {
            //always assume that length1 is equal or smaller than length2
            if (length1 > length2)
            {
                return FindKthSmallestElement_BinarySearch(array2, start2, length2, array1, start1, 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;

            int firstNode1 = start1 + half_k - 1;
            int firstNode2 = start2 + rest_kElements - 1;

            if (array1[firstNode1] == array2[firstNode2])
            {
                return array1[firstNode1];
            }

            if (array1[firstNode1] < array2[firstNode2]) // remove half_k
            {
                // Go to solve a smaller subproblem, remove first part of the array1
                int newStart   = half_k;
                int newLength  = length1 - half_k; 
                int searchNew  = k - half_k;

                return FindKthSmallestElement_BinarySearch(
                    array1, 
                    newStart, 
                    newLength, 
                    array2, 
                    start2, 
                    length2, 
                    searchNew);
            }
            else   // remove rest_kElements
            {   
                // Go to solve a smaller subproblem, remove first part of the array2
                int newStart  = rest_kElements;
                int newLength = length2 - rest_kElements; 
                int searchNew = k - rest_kElements;

                return FindKthSmallestElement_BinarySearch(
                    array1, 
                    start1, 
                    length1, 
                    array2, 
                    newStart, 
                    newLength, 
                    searchNew);
            }
        }       
    }
}

Fix the bug of time complexity issue, avoid array's copy.