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.
vedic-kalra
commented
2 years ago
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
Checklist:
README.md