# Is my algorithm to find the median of 2 sorted arrays O(log(m + n))?

I came up with a solution for LeetCode Problem 4:
Median of Two Sorted Arrays

The expected efficiency of this should be $$O(\log(m+n))$$, where $$m$$ and $$n$$ are the lengths of nums1 and nums2.

For my solution I decided only to process only the first half of nums1 and nums2.
Does that count as logarithmic time, or is it still linear time?

My Java code:

class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Don't need the entire array - only the first half
int maxSize = nums1.length + nums2.length;
int size = maxSize / 2 + 1;

// Merged array and its index
int[] merged = new int[size];
int m = 0;

// Left index, right index
int l = 0;
int r = 0;

// Build the merged array
while (m < merged.length) {
if (l >= nums1.length) {
// Left array exhausted - just add the right array
merged[m] = nums2[r];
m++;
r++;
} else if (r >= nums2.length) {
// Vice versa
merged[m] = nums1[l];
m++;
l++;
} else {
// Compare left and right
int a = nums1[l];
int b = nums2[r];

if (a > b) {
merged[m] = b;
m++;
r++;
} else {
merged[m] = a;
m++;
l++;
}
}
}

// Debug
// for (int x : merged) {
//     System.out.print(x + ", ");
// }
// System.out.println();

// Find median based on the first half
if (maxSize % 2 == 0) {
// Divide with 2.0 instead of 2: important!
return (merged[size-1] + merged[size-2]) / 2.0;
} else {
return merged[size-1];
}
}
}


Pseudocode:

• Make a new array $$m$$, which is the size of the first half of both arrays combined

• Merge both arrays together in the correct order into the array $$m$$
(note that this will not fully iterate the first or second array, since $$m$$ is only the size of the first half of both combined arrays)

• Return the last element of 'm', or the average of the 2 last elements of $$m$$ (the median of both sorted arrays)

Leetcode result:

Runtime: 2 ms, faster than 99.75% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 40.1 MB, less than 81.65% of Java online submissions for Median of Two Sorted Arrays.

• Can you describe your algorithm without using Java? Jan 16, 2021 at 16:54
• I have updated the post to explain the algorithm using pseudocode and removed the comment about binary search since it was confusing. What I was trying to say is that just like binary search is O(log(n)) because it divides the array in half each time, my algorithm only processes the first half of the merged array to find the median. Jan 16, 2021 at 18:10

Judging from your description and your code, you are basically doing a merge of the two array but stop at the median. This means that your main loop (body) is executed $$(m + n) / 2 \in O(m + n)$$ times, which is linear in $$m + n$$. You could also figure that one out experimentally by trying your algorithm on a range of different inputs and plotting the time taken against $$m + n$$, I guess.
If you want to find a solution which takes $$O(\log (m + n))$$ time you could try working backwards: A binary search over a (sorted) array of length $$n$$ takes $$O(\log(n))$$ time.