Find kth largest element in the union of two sorted array (Follow up)

Problem statement:

Find \$kth\$ largest element in the union of two sorted array, assuming that two sorted arrays are in ascending order. The size of two arrays are \$m\$, \$n\$.

My introduction of the algorithm

To solve the kth largest element in the union of two sorted array, there are three solutions; \$1\$: The trivial way, time complexity is \$O(m+n)\$; \$2\$: A better way is with time complexity \$O(k)\$; \$3\$: The best solution, but non-trivial is with the time complexity \$O(lg m + lg n)\$ where \$m\$, \$n\$ are the length of two arrays.

I solved two issues in my last practice. First, make sure that the largest kth element is found instead of the smallest kth element. Secondly, the time complexity is \$O(lg m + lg n)\$, pass the array's position index instead of copying the array costing \$O(m)\$ or \$O(n)\$.

The practice is advised by the comment from JS1 Jan 9 on my last practice. "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)\$ or \$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 \$(logk)\$ time."

```
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

Your code looks really good, but there are some things I'm not necessarily a fan of:

private static double FindKthSmallestElement_BinarySearch(
   int[] array1,
   int   start1, 
   int   length1,
   int[] array2,
   int   start2, 
   int   length2,
   int   k)

This reminds me of the C/C++ days and when I did DirectX programming. Every single method had the parameters listed out like this because we didn't have the powerful Intellisense then, and it was easy to lay them out in headers like this to allow us to reference easily. But it's 2017, and this is C#, we don't need to lay things out like this, it should be a red flag that we're doing something wrong.

And what may be that 'wrong' thing? We're not encapsulating our data. The fact that we have three variables with a suffix of 1 or 2 tells us that we could encapsulate those and save ourselves several parameters, since they're co-dependent.

public class SearchArray
{
    public int[] Array { get; set; }
    public int Start { get; set; }
    public int Length { get; set; }
}

The interesting thing here is we may get an increase in performance by making this array mutable, but at least it shortens our method prototype:

public static double FindKthSmallestElement_BinarySearch(SearchArray array1, SearchArray array2, int k)

The rest of it looks great. I won't comment on the algorithm, because I'm not an algorithms person, and it looks like it does what it wants.

What I'm even more interested in is the fact that you wrote this algorithm so clearly that it's easy to follow and read. Personally, I think more people should take that page out of this playbook and write code for clarity first, then deal with whatever issues may arise.

StackExchange Code Review Q#154867, answer score: 4