Median of Two Sorted Arrays
ID: 4; hard
Last updated
ID: 4; hard
Last updated
We use divide and conquer in this problem. We change the problem to find the k-th number of two sorted arrays, where k represents the index of the median.
Inside the helper method,
If either A or B runs out of elements first, then we just use the current k-th element of the other array.
If k == 1, which means we need the first number, then we pick the smaller one from A or B.
Then we count half of k steps for both A and B. We shrink the range based on which one is smaller. Note we only update the index for the array with the smaller element and also do not forget to update k.