Find kth largest element in the union of two sorted array

Question

Problem statement: Find \$kth\$ largest element in the union of two sorted array.

My introduction of the algorithm I spent a few hours to review two algorithms, Leetcode 4:Median of Two Sorted Arrays and Leetcode 215:Kth Largest Element in an Array together since median is a special case of kth element problem, and also read the article to talk about the kth largest element in the union of two sorted array, 3 solutions: 1:The trivial way, \$O(m+n)\$; 2: A better way, O(k); 3: The best solution, but non-trivial, O(lg m + lg n).

So, I decided to practice the algorithm "Find kth largest element in the union of two sorted array" (similar to Leetcode 4 and 215, but with some difference.), using binary search non-trivial one, C# Source code. Please help me to review the code.

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[] { };
        }
    }
}

Answer 1

Can't comment yet, so a few clarifications:

1. Isn't your test RunSampleTestcase1() incorrect? The fifth largest value would be 6. You appear to be returning the 5th smallest value. Also evidenced by return Math.Min(array1[0], array2[0]);. I'd think the k^th largest should be return Math.Max(array1[array1.Length - 1], array2[array2.Length - 1]).

2. Why are you passing length as a parameter to FindKthLargestElement_BinarySearch()? Arrays already have a length parameter. Using that will make the code much easier to follow.

3. Why are you reinventing the wheel with ArraySplice()?

---

Note: All of these have one big red flag though. That article you linked is referencing arrays; however, it discusses using linked lists in the Big O notation. Those have a lot different properties than arrays in C#.