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

Question

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.

Answer 1

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.