pranjay-poddar
4. Median of Two Sorted Arrays
Updated solution: Variant of binary search in C++, 14[ms] ; O(lg(m+n)) Easy to understand with explanation.
Description
Suppose the two arrays are A and B. Perform the following variant of binary search first in A then B to find the median.
Start from low = 0, high = |A|, guess i = floor (low + high)/2 For the median m, there should be total half = floor (|A| + |B| + 1) / 2 elements not greater than it. Since there are i + 1 elements not greater than A[i] in A, There should be half - (i + 1) elements not greater than A[i] in B. Denote j = half - i - 2, thus we can compare if B[j] <= A[i] <= B[j + 1] is satisfied. This indicates That the guess is the correct median.
Otherwise, we can easily tell if the guess is too small or too big, then halve the elements to adjust the guess.
Fixes #134
Type of change
- [ ] New feature/solution added
Checklist:
- [x] My code follows the style guidelines(Clean Code) of this project
- [x] I have performed a self-review of my own code
- [x] I have commented my code, particularly in hard-to-understand areas
- [] I have created a helpful and easy to understand
README.md - [] I have made corresponding changes to the documentation
- [x] My changes generate no new warnings
- [] I have updated the readme with tick in question in appropriate language.
