Thanks. :)
@lzjknight said in Share my O(log(min(m,n)) solution with explanation:
Contributed to your 600th like :)
Thanks. :)
@lzjknight said in Share my O(log(min(m,n)) solution with explanation:
Contributed to your 600th like :)
@0x0101 Because I have to make sure j is non-nagative since 0 <= i <= m and j = (m + n + 1)/2 - i. If n < m , then j may be nagative, that will lead to wrong result.
I read the link you provided, and was surprised by the fact that big-O is completely different with little-o. Thank you for telling me that.
@StefanPochmann said in Share my o(log(min(m,n)) solution with explanation:
@MissMary A little request: Could you fix your title? Your solution isn't o(log(min(m,n)) but O(log(min(m,n)). Big-O and little-o aren't the same.
Hi @StefanPochmann . I have changed the title. Thanks.
@xyao01 @rahulthankachan I must make n >= m
because I have to make sure j
is always non-nagative since 0 <= i <= m
and j = (m + n + 1)/2 - i
. If n < m
, then j
may be nagative, that will lead to a wrong result.
Hi, @doudou900914 . I think you can't remove the corner testing for j
in the final block.
@rahulthankachan You need to change "iMin++" to "iMin = i + 1", "iMax--" to "iMax = i - 1". So the size of the searching range [iMin, iMax] will be reduced by half after a loop. Otherwize, the size will be reduced by only 1.
@Quentin.chen Thank you very much for telling me this. I think it it really a good improvement. I have improved my original code and it passed all the tests.
However, although I believe the improved code will run faster, because I changed:
if j > 0 and i < m and B[j-1] > A[i]: ...
to:
if i < m and B[j-1] > A[i]: ...
But the improved code runs a little slower.
@shanzhihaoszh j = (m + n + 1)/2 - i
is deduced from the equation i + j == m - i + n - j (or: m - i + n - j + 1)