Binary Search: K-th Element of Two Sorted Arrays

1. Problem Statement & Context

Building directly upon the foundational problem of finding the Median of Two Sorted Arrays, this chapter tackles the generalized problem: finding the K-th element after hypothetically merging two sorted arrays of different sizes.

• Input: Two sorted arrays (array1 and array2) of sizes $N_1$ and $N_2$, and an integer $K$ ($1 \le K \le N_1 + N_2$).
• Objective: Return the element that would occupy the $K$-th position if the two arrays were merged into a single sorted array.
• Crucial Constraint: You are not required to physically merge the arrays. Doing so would cost $O(N_1 + N_2)$ time. The goal is to achieve an optimal $O(\log(\min(N_1, N_2)))$ time complexity using Binary Search.

2. Why the Previous Median Concept is Vital

If you attempt to solve this problem without mastering the median-of-two-sorted-arrays pattern, the logic will feel opaque. The median problem is simply a specific case of the $K$-th element problem where:

• If total elements $N_1 + N_2$ is odd, the median is the single middle element ($K = \frac{N_1 + N_2 + 1}{2}$).
• If total elements $N_1 + N_2$ is even, the median is the average of two middle elements.

By generalizing this partitioning technique, we can locate any arbitrary $K$-th element efficiently.

3. Core Mental Model: Partitioning for the K-th Element

Imagine two sorted arrays, array1 and array2. When we look for the $K$-th element in the hypothetical merged array, we are effectively trying to split the combined elements into two logical halves:

1. Left Half: Exactly $K$ elements total (contributed from array1 and array2).
2. Right Half: The remaining $(N_1 + N_2 - K)$ elements.

Real-Life Analogy: Combining Two Queues

Think of two separate ticket queues (array1 and array2), both already sorted by ticket priority. If an event coordinator steps out and announces, "I want to let exactly $K$ people inside right now," those people will come from the front of both queues.

To figure out who the last person let in was (which is our $K$-th element), we just need to test different split sizes—taking $l_1$ people from Queue 1 and $K - l_1$ people from Queue 2—ensuring that everyone let in has a higher priority than anyone left outside.

4. Visualizing the Partition and Left-Half Formation

Let us partition array1 taking l elements, which means we must take K - l elements from array2 to ensure our left partition contains exactly $K$ elements.

For this partition to be valid (meaning all elements on the left are smaller than or equal to all elements on the right), two crossover conditions must hold true:

1. array1[l - 1] <= array2[K - l] (Max of left from A $\le$ Min of right from B)
2. array2[K - l - 1] <= array1[l] (Max of left from B $\le$ Min of right from A)

Once this valid cut is found, what is the $K$-th element? The $K$-th element is the maximum element of the left half, because the left half contains exactly $K$ elements, and the largest among them must sit right at the boundary (position $K$).

Where L1 is the last element taken from array1's left partition, and L2 is the last element taken from array2's left partition.

5. Refining Binary Search Bounds (Low and High)

In the median problem, our left partition size was fixed at roughly $\frac{N_1 + N_2}{2}$. Here, our left partition size is fixed at $K$. This changes our search space boundaries (low and high for array1 elements).

Why Naive Bounds Fail

If we blindly set low = 0 and high = N1, we run into edge cases:

• What if $K = 7$, but array1 only has 5 elements? We cannot pick 7 elements from array1.
• What if $K = 7$, and array2 only has 3 elements? Even if we pick all 3 elements from array2, we still need at least $7 - 3 = 4$ elements from array1. We cannot pick 0 elements from array1.

Correct Boundary Formulas

1. low (Minimum elements we must pick from array1):

   • At least $0$, but if $K > N_2$, we are forced to pick at least $K - N_2$ from array1.
   • $\text{low} = \max(0, K - N_2)$

2. high (Maximum elements we can pick from array1):

   • We cannot pick more than $N_1$ elements, nor can we pick more than $K$ elements in total.
   • $\text{high} = \min(K, N_1)$

6. Complete Implementation (C++)

Here is the robust, production-ready C++ solution adapted from the median binary search template:

#include <bits/stdc++.h>
using>

class Solution {
public:
    double kthElement(vector<int>& a, vector<int>& b, int n1, int n2, int k) {
        // Ensure 'a' is the smaller array to minimize binary search range
        if (n1 > n2) {
            return kthElement(b, a, n2, n1, k);
        }
        
        // Binary search bounds on array 'a'
        int low = max(0, k - n2);
        int high = min(k, n1);
        
        while (low <= high) {
            int cut1 = (low + high) >> 1; // Number of elements taken from array 'a'
            int cut2 = k - cut1;          // Number of elements taken from array 'b'
            
            // Define left and right boundary values
            int l1 = (cut1 == 0) ? INT_MIN : a[cut1 - 1];
            int l2 = (cut2 == 0) ? INT_MIN : b[cut2 - 1];
            
            int r1 = (cut1 == n1) ? INT_MAX : a[cut1];
            int r2 = (cut2 == n2) ? INT_MAX : b[cut2];
            
            // Check if partition is valid
            if (l1 <= r2 && l2 <= r1) {
                // The K-th element is the maximum of the left partition elements
                return max(l1, l2);
            }
            else if (l1 > r2) {
                // We took too many elements from array 'a', shift search left
                high = cut1 - 1;
            } 
            else {
                // We took too few elements from array 'a', shift search right
                low = cut1 + 1;
            }
        }
        
        return 0; // Dummy return for compilation safety
    }
};

7. Step-by-Step Flow Walkthrough

Let's trace how the algorithm executes when searching for $K = 4$ across two sorted arrays: A = [1, 4, 7, 10, 12] ($N_1 = 5$) and B = [2, 3, 6, 15] ($N_2 = 4$).

A: [1, 4, 7, 10, 12]
B: [2, 3, 6, 15]
K = 4

1. Calculate Bounds:
   • low = max(0, 4 - 4) = 0
   • high = min(4, 5) = 4
2. Iteration 1:
   • cut1 = (0 + 4) / 2 = 2 (Take 2 elements from A: [1, 4])
   • cut2 = 4 - 2 = 2 (Take 2 elements from B: [2, 3])
   • Left elements: l1 = 4, l2 = 3
   • Right elements: r1 = 7, r2 = 6
   • Check condition: Is l1 <= r2 ($4 \le 6$) and l2 <= r1 ($3 \le 7$)? Yes!
   • Result: max(l1, l2) = max(4, 3) = 4.
3. Execution Complete: Returns 4 instantly in $O(\log(\min(N_1, N_2)))$ time without merging arrays.

8. Complexity Analysis

Summary and Key Takeaways

• Concept Extension: Finding the $K$-th element is a direct generalization of the median-of-two-sorted-arrays problem, where the left partition size is fixed at $K$ instead of $\frac{N_1 + N_2}{2}$.
• Zero Merging Required: Avoid physical array merging ($O(N_1 + N_2)$) in favor of binary searching the partition boundaries.
• Dynamic Bounds: Unlike the median problem where low = 0 and high = N1, the $K$-th element requires adjusted bounds: low = max(0, K - N2) and high = min(K, N1) to prevent out-of-bound errors when $K$ is exceptionally small or large.
• Partition Validation: A correct cut is established when l1 <= r2 and l2 <= r1.
• Final Answer Extraction: Because the left partition contains exactly $K$ elements, the $K$-th element is always the maximum value of the left boundary elements: max(l1, l2).
• Array Symmetry Optimization: Always run the binary search on the smaller array (N1 <= N2) to guarantee optimal $O(\log(\min(N_1, N_2)))$ time complexity.
• Avoid Memorization: Focus on understanding the mental model of splitting combined elements into left and right halves rather than memorizing formulaic code.