Find K-th Element of Two Sorted Arrays Optimal Binary Search Approach

Given two sorted arrays arr1 and arr2, and a number k, your task is to find the K-th smallest element in the merged array formed by combining both arrays.

• Both arrays are individually sorted in non-decreasing order.
• You are not allowed to fully merge the arrays or use extra space.
• Find the result using an efficient approach.

If either array is empty, the answer will depend entirely on the other array. If k is invalid (e.g., larger than total elements), return -1.

Understanding the Problem

We are given two sorted arrays and a number k. Our goal is to find the k-th smallest element in the combined sorted form of these two arrays. But we are not supposed to merge them completely.

For a beginner, imagine placing all elements from both arrays into one big array and sorting it. Then, the k-th element is simply at index k - 1. But this is inefficient. So instead, we use a smart trick called binary search to figure out the answer without merging.

Step-by-Step Solution with Example

Step 1: Choose an Example

Let’s take arr1 = [2, 3, 6, 7, 9] and arr2 = [1, 4, 8, 10], and we want to find k = 5.

If we merge and sort: [1, 2, 3, 4, 6, 7, 8, 9, 10], the 5th smallest element is 6. We’ll now try to find 6 without merging.

Step 2: Always Binary Search the Smaller Array

We always do binary search on the smaller array to keep the process efficient. In our case, arr2 is smaller (4 elements), so we search there.

Step 3: Understand the Partition Logic

We divide arr2 such that we take cut2 elements from it and cut1 = k - cut2 from arr1.

We want all elements on the left side (from both arrays) to be less than or equal to the elements on the right side. We compare the largest on the left and the smallest on the right to check this.

Step 4: Perform Binary Search

We initialize low = max(0, k - len(arr1)) and high = min(k, len(arr2)).

We perform binary search between low and high, computing cut2 in the middle, and getting cut1 = k - cut2.

We extract four values:

• l1 = -Infinity if cut1 == 0 else arr1[cut1 - 1]
• l2 = -Infinity if cut2 == 0 else arr2[cut2 - 1]
• r1 = Infinity if cut1 == len(arr1) else arr1[cut1]
• r2 = Infinity if cut2 == len(arr2) else arr2[cut2]

We check if l1 ≤ r2 and l2 ≤ r1. If true, the answer is max(l1, l2).

If l1 > r2, move left: high = cut2 - 1. If l2 > r1, move right: low = cut2 + 1.

Step 5: Return the Final Answer

When the correct partition is found, return max(l1, l2) as the k-th smallest element.

Edge Cases

Empty Array

If one array is empty, just return the k-th element from the other array directly.

Example: arr1 = [], arr2 = [5, 7, 9], k = 2 → Answer is 7.

K is Out of Range

If k > len(arr1) + len(arr2), it's invalid. We return -1 or a suitable error message.

All Elements are Same

Even if all elements are the same, the logic still works. The partitions will respect the counts, not the values.

Highly Unbalanced Lengths

Even if one array is very short and the other is long, binary search will happen on the smaller one, so performance remains efficient.

Finally

This approach avoids merging the arrays completely and instead finds the correct "cut" using binary search. This gives us a time complexity of O(log(min(n, m))), which is much faster than the naive approach.

By handling edge cases smartly and applying partitioning logic carefully, we can find the k-th smallest element in two sorted arrays in a time-efficient and space-efficient manner, perfect for both interviews and real-world problems.

1. Let arr1 be the smaller array among the two. If not, swap arr1 and arr2.
2. Let n = arr1.length and m = arr2.length.
3. Set low = max(0, k - m) and high = min(k, n).
4. While low ≤ high, do:
5. → Set cut1 = (low + high) / 2, cut2 = k - cut1.
6. → Use l1 = -∞ if cut1 == 0, else arr1[cut1 - 1].
7. → Use l2 = -∞ if cut2 == 0, else arr2[cut2 - 1].
8. → Use r1 = ∞ if cut1 == n, else arr1[cut1].
9. → Use r2 = ∞ if cut2 == m, else arr2[cut2].
10. If l1 ≤ r2 and l2 ≤ r1, return max(l1, l2).
11. Else if l1 > r2, move left: high = cut1 - 1.
12. Else, move right: low = cut1 + 1.

O(1)

Explanation: Only a constant amount of additional variables are used for computation and control.