Find median of two sorted arrays Problem statement

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be \$\mathcal{O}(\log (m+n))\$.

Implementation

 def median(A, B):
    m, n = len(A), len(B)
    if m &gt; n:
        A, B, m, n = B, A, n, m
    if n == 0:
        raise ValueError

    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin &lt;= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if j &gt; 0 and i &lt; m and B[j-1] &gt; A[i]:
            # i is too small, must increase it
            imin = i + 1
        elif i &gt; 0 and j &lt; n and A[i-1] &gt; B[j]:
            # i is too big, must decrease it
            imax = i - 1
        else:
            # i is perfect
            if i == 0: max_of_left = B[j-1]
            elif j == 0: max_of_left = A[i-1]
            else: max_of_left = max(A[i-1], B[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = B[j]
            elif j == n: min_of_right = A[i]
            else: min_of_right = min(A[i], B[j])

            return (max_of_left + min_of_right) / 2.0


Concern

I suspect that it is safe to change this line of code

j &gt; 0 and i &lt; m and B[j-1] &gt; A[i]


to

i &lt; m and B[j-1] &gt; A[i]


and also it is safe to change this line of code

i &gt; 0 and j &lt; n and A[i-1] &gt; B[j]


to 

i &gt; 0 and A[i-1] &gt; B[j]


I think remove the condition check of j is safe since we already making sure size of A is no bigger than size of B.
Sorry for being late, but had no time to study your code until today.
The results are the same which AmirHossein presented before.

After you conditionally swap the input arrays:

    if m &gt; n:
        A, B, m, n = B, A, n, m


you have m &lt;= n, so

    half_len = (m + n + 1) // 2


(after the fix by AmirHossein) is not less than m. That makes

    j = half_len - i


greater than zero if i &lt; m, so j &gt; 0 and i &lt; m is redundant.

Of course half_len is also is not greater than n, so similary j &lt; n if i &gt; 0.

As for the complexity, the code bisects the A array in each iteration, so the complexity is actually \$\mathcal{O}(\log m)\$ where m is the length of A after the conditional swap, or \$\mathcal{O}(\log (\min(m,n)))\$ in terms of input values of m,n. And this can be bounded by \$\mathcal{O}(\log (m+n))\$.