Finding the k-th Smallest Element in Two Sorted Arrays

You are given two sorted arrays, which may contain duplicate elements, and an integer \(k\). Your task is to determine the \(k\)th smallest element in the combined sorted sequence of these two arrays. To achieve efficiency, your algorithm should run in better than \(O(m+n)\) time, where \(m\) and \(n\) are the sizes of the first and second arrays respectively.

The problem requires the use of an efficient divide and conquer method (binary search method) to locate the desired element without the need to fully merge the two arrays.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains three integers: \(m\), \(n\) and \(k\), where \(m\) and \(n\) denote the number of elements in the first and second sorted arrays respectively, and \(k\) is the order of the smallest element to find.
• The second line contains \(m\) integers representing the first sorted array. If \(m = 0\), this line will be empty.
• The third line contains \(n\) integers representing the second sorted array.

outputFormat

Output the \(k\)th smallest element from the merged sorted array on standard output (stdout).

3 3 5
1 3 8
2 7 10

8