04 Median of Two Sorted Arrays

Description

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

First Thought

It would be pretty easy just to use a O(n) merge and then pick the middle point. However, this problem requires a O(log (m+n)) time complexity.

I haven’t come up with the solution and searched online and it explains this problem crestal clear:

Median of two sorted arrays with different sizes in O(log(min(n, m))) - GeeksforGeeks

I’ll try to explain it myself (, as a practice of English writing).

penway Wang
penway Wang
Mechanic Technical Director

My research interests include computer vision, artificial intelligence and software engineering. I am a FSAE race car crew member at the same time, designing suspension system.

Next
Previous