4. Median of Two Sorted Arrays [分治]

https://leetcode.com/problems/median-of-two-sorted-arrays/
相当经典的题目，需要仔细想清楚各种条件，以及将想法实践出来。

个人解答

class Solution:
    def findMedianSortedArrays(self, a: List[int], b: List[int]) -> float:
        if len(a) > len(b):
            a, b = b, a
        m, n = len(a), len(b)
        # one array is empty
        if m == 0:
            return b[n // 2] if n % 2 == 1 else (b[n // 2 - 1] + b[n // 2]) / 2
        l, r = 0, m
        while l <= r:
            i = (l + r) // 2 # a's cut position
            j = (m + n + 1) // 2 - i # b's cut position, determined by i
            # two array divided into two parts resplectively
            # a[0:i - 1] | a[i:]
            # b[0:j - 1] | b[j:]
            # valid condition: a[i - 1] <= b[j] and b[j - 1] <= a[i]
            if i > 0 and a[i - 1] > b[j]:
                # i too large
                r = i - 1
            elif i < m and b[j - 1] > a[i]:
                # i too small
                l = i + 1
            else:
                # valid i
                # print(i, j)
                lval = max(a[i - 1] if i > 0 else -math.inf, b[j - 1] if j > 0 else -math.inf)
                rval = min(a[i] if i < m else math.inf, b[j] if j < n else math.inf)
                if (m + n) % 2 == 1:
                    return lval
                else:
                    return (lval + rval) / 2

题目分析

https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn)))-solution-with-explanation))-solution-with-explanation)
https://zhuanlan.zhihu.com/p/70654378

首先很容易想到分治的，也能想到，两者相互比较，然后调整区间。
但是，想明确定义出来还是需要费劲的。

第一点，两个数组的当前值看似是两个变量，其实是一个，因为i定了，j肯定就定了。
第二点，理清楚需要满足的条件，也就是，a数组和b数组左侧的都要必须小于右侧的两个数组，而这其实由于i和j的关系，处理起来并没有想的那么困难。

剩下就是一些边界情况的处理了，如果理得清楚，写出来还是很优雅的。