Find the K-th Element of Two Sorted Arrays Using Binary Search in Java

Finding the K-th element of two sorted arrays is a common algorithm problem that tests your understanding of arrays, binary search, partitioning, and divide-and-conquer techniques.

The straightforward solution is to merge both sorted arrays and then find the element at position k. However, merging the arrays requires additional time and, depending on the implementation, extra memory.

A more efficient approach is to use binary search on the smaller array. This allows us to find the K-th element without actually merging the two arrays.

In this article, we will understand the binary search approach step by step and implement it in Java.

Problem Statement

Given two sorted arrays a[] and b[], and an integer k, find the K-th element in the sorted array that would result from merging both arrays.

The arrays are already sorted in ascending order.

For example:

a = [2, 3, 6, 7, 9]
b = [1, 4, 8, 10]
k = 5

If we merge the two arrays, the result is:

[1, 2, 3, 4, 6, 7, 8, 9, 10]

The 5th element is:

Therefore, the answer is 6.

Consider another example:

a = [1, 4, 8, 10, 12]
b = [5, 7, 11, 15, 17]
k = 6

The merged array would be:

[1, 4, 5, 7, 8, 10, 11, 12, 15, 17]

The 6th element is:

Therefore, the answer is 10.

Naive Approach

The simplest approach is to merge the two arrays into a new sorted array and then return the element at index k - 1.

If the first array contains n elements and the second array contains m elements, the merged array contains n + m elements.

The time complexity is:

O(n + m)

The approach can also require:

O(n + m)

additional space if a new array is created.

Although this approach is easy to understand, it does unnecessary work because we only need one element from the merged result.

We can improve this using binary search.

Binary Search Approach

The main idea is to divide the two arrays into two parts:

Left Part | Right Part

We want exactly k elements to be present in the combined left part.

Suppose we select cut1 elements from array a. Then we need:

cut2 = k - cut1

elements from array b.

The goal is to find a partition where all elements on the left side are less than or equal to all elements on the right side.

For example:

Array A:
[1, 4, 8 | 10, 12]

Array B:
[5, 7, 11 | 15, 17]

If the total number of elements on the left is k, then the K-th element is the largest element on the left side.

Why Binary Search Is Applied to the Smaller Array

We always perform binary search on the smaller array.

Suppose:

n = a.length
m = b.length

If n > m, we swap the arrays.

This gives us:

n <= m

Searching the smaller array keeps the binary-search range as small as possible and gives the required complexity of:

O(log(min(n, m)))

Finding the Valid Partition

For every possible partition, we need four values:

left1  = largest element on the left side of array A
right1 = smallest element on the right side of array A

left2  = largest element on the left side of array B
right2 = smallest element on the right side of array B

The partition is correct when:

left1 <= right2

and

left2 <= right1

When both conditions are true, the K-th element is:

max(left1, left2)

This works because there are exactly k elements on the combined left side.

Handling Array Boundaries

There are cases where the partition can be at the beginning or end of an array.

For example, if cut1 == 0, there is no element on the left side of array A.

Instead of adding special conditions throughout the algorithm, we can use:

Integer.MIN_VALUE

as the left boundary.

Similarly, if cut1 == n, there is no element on the right side of array A, so we can use:

Integer.MAX_VALUE

The same technique is used for array B.

This allows the partition comparison to work consistently.

Step-by-Step Algorithm

The complete logic can be broken down into the following steps.

Step 1: Identify the Array Sizes

Get the lengths of both arrays:

int n = a.length;
int m = b.length;

Step 2: Use the Smaller Array for Binary Search

If the first array is larger, swap the arrays by calling the same method with the parameters reversed.

if (n > m) {
    return kthElement(b, a, k);
}

Now a is guaranteed to be the smaller array.

Step 3: Define the Binary Search Range

The lower and upper limits are calculated as:

int low = Math.max(0, k - m);
int high = Math.min(k, n);

The lower boundary ensures that we do not take more than m elements from array B.

The upper boundary ensures that we do not take more than n elements from array A.

Step 4: Calculate the Partitions

Inside the binary search, calculate the first partition:

int cut1 = low + (high - low) / 2;

The second partition is determined automatically:

int cut2 = k - cut1;

Together:

cut1 + cut2 = k

Therefore, exactly k elements are present on the left side.

Step 5: Find the Boundary Values

Calculate the four values around the partitions:

int left1 = (cut1 == 0)
    ? Integer.MIN_VALUE
    : a[cut1 - 1];

int left2 = (cut2 == 0)
    ? Integer.MIN_VALUE
    : b[cut2 - 1];

int right1 = (cut1 == n)
    ? Integer.MAX_VALUE
    : a[cut1];

int right2 = (cut2 == m)
    ? Integer.MAX_VALUE
    : b[cut2];

These values allow us to determine whether the partition is valid.

Step 6: Check Whether the Partition Is Correct

The partition is valid when:

left1 <= right2 && left2 <= right1

If this condition is true, the answer is:

Math.max(left1, left2)

Step 7: Adjust the Binary Search

If:

left1 > right2

the partition in array A is too far to the right.

Therefore, move the upper boundary:

high = cut1 - 1;

Otherwise, the partition needs to move to the right:

low = cut1 + 1;

The process continues until the correct partition is found.

Java Implementation

Here is the complete implementation:

class Solution {

    public int kthElement(int a[], int b[], int k) {

        int n = a.length;
        int m = b.length;

        // Always perform binary search on the smaller array
        if (n > m) {
            return kthElement(b, a, k);
        }

        // Define the valid range for partition in array A
        int low = Math.max(0, k - m);
        int high = Math.min(k, n);

        while (low <= high) {

            // Partition of array A
            int cut1 = low + (high - low) / 2;

            // Partition of array B
            int cut2 = k - cut1;

            // Elements immediately before the partitions
            int left1 = (cut1 == 0)
                    ? Integer.MIN_VALUE
                    : a[cut1 - 1];

            int left2 = (cut2 == 0)
                    ? Integer.MIN_VALUE
                    : b[cut2 - 1];

            // Elements immediately after the partitions
            int right1 = (cut1 == n)
                    ? Integer.MAX_VALUE
                    : a[cut1];

            int right2 = (cut2 == m)
                    ? Integer.MAX_VALUE
                    : b[cut2];

            // Correct partition found
            if (left1 <= right2 && left2 <= right1) {
                return Math.max(left1, left2);
            }

            // Partition in array A is too far right
            else if (left1 > right2) {
                high = cut1 - 1;
            }

            // Partition in array A is too far left
            else {
                low = cut1 + 1;
            }
        }

        return -1;
    }
}

Understanding the Algorithm with an Example

Consider:

a = [2, 3, 6, 7, 9]
b = [1, 4, 8, 10]
k = 5

The first array has 5 elements and the second has 4 elements, so the arrays are swapped internally because binary search should be performed on the smaller array.

The smaller array is:

[1, 4, 8, 10]

The algorithm searches for a partition where exactly five elements are present on the left.

Suppose the partitions are:

A: [1, 4 | 8, 10]

B: [2, 3, 6 | 7, 9]

The boundary values are:

left1  = 4
right1 = 8

left2  = 6
right2 = 7

Now check:

left1 <= right2
4 <= 7

and:

left2 <= right1
6 <= 8

Both conditions are true.

Therefore, the K-th element is:

max(4, 6) = 6

So the answer is:

Complexity Analysis

The binary search is performed only on the smaller array.

Therefore, the time complexity is:

O(log(min(n, m)))

The algorithm does not create another array and only uses a fixed number of variables.

Therefore, the auxiliary space complexity is:

O(1)

This is significantly more efficient than explicitly merging both arrays when the input arrays are large.

Binary Search vs. Merge Approach

Feature	Merge Approach	Binary Search Approach
Time Complexity	O(n + m)	O(log(min(n, m)))
Extra Space	O(n + m) if a new array is created	O(1)
Implementation	Easier	More complex
Arrays Must Be Sorted	Yes	Yes
Suitable for Large Arrays	Less efficient	More efficient
Main Technique	Merge	Binary Search and Partitioning

Common Mistakes

Performing Binary Search on the Larger Array

The algorithm should search the smaller array. This keeps the search space minimal and simplifies the partition boundaries.

Using the Wrong Partition Range

The range should be calculated using:

int low = Math.max(0, k - m);
int high = Math.min(k, n);

Using an incorrect range can result in an invalid cut2.

Forgetting the K-th Position Is 1-Based

If the problem states that k = 1, the required element is the smallest element among both arrays.

The partition logic in this implementation uses k as the number of elements that must exist on the left side.

Ignoring Empty Partition Cases

A partition can occur at the beginning or end of an array. The implementation handles these cases using:

Integer.MIN_VALUE

and:

Integer.MAX_VALUE

Merging the Arrays Unnecessarily

If only the K-th element is required, creating a complete merged array performs unnecessary work.

Applications of This Technique

The partition-based binary search technique is useful beyond this particular problem.

It can help with problems involving:

Finding the median of two sorted arrays
Finding K-th smallest elements
Searching across multiple sorted data sources
Efficient processing of large sorted datasets
Divide-and-conquer based searching problems

The same partitioning idea is particularly useful when the input data is already sorted and only a specific position or boundary needs to be determined.

Conclusion

Finding the K-th element of two sorted arrays can be solved efficiently without merging the arrays. The key idea is to partition both arrays so that exactly k elements are present on the left side.

By performing binary search on the smaller array, we can efficiently find the correct partition. Once the partition satisfies:

left1 <= right2

and:

left2 <= right1

the K-th element is simply the larger value from the two left partitions.

The final solution has a time complexity of O(log(min(n, m))) and uses O(1) auxiliary space.

Understanding this technique is valuable for coding interviews and for solving other problems involving sorted arrays, binary search, and partition-based algorithms.