二分查找

前提是必须有序

https://zh.wikipedia.org/zh-hans/%E4%BA%8C%E5%88%86%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95

在计算机科学中，二分查找算法（英语：binary search algorithm），

也称折半搜索算法（英语：half-interval search algorithm）[1]、对数搜索算法（英语：logarithmic search algorithm）[2]，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

当需要在两个有序数组中找到中位数时，我们可以利用二分查找的思想来解决这个问题。下面是一个详细解释和示意图：

    假设我们有两个有序数组 nums1 和 nums2，长度分别为 m 和 n。为了简化问题，我们假设 m <= n。
    我们定义一个变量 left，其初始值为 0，表示 nums1 的左边界。定义一个变量 right，其初始值为 m，
    表示 nums1 的右边界。我们需要在 nums1 中找到一个位置 i，使得 nums1(0) 到 nums1(i-1) 和 nums2(0) 到 nums2(j-1)
    组成的所有元素合并后能够排在整个合并数组的左半部分。这里 j = (m + n + 1) / 2 - i。

    为了找到合适的位置 i，我们可以利用二分查找的思想。在每一轮迭代中，我们通过二分查找的方法调整 i 的值，
    然后根据 i 和 j 计算出左半部分的最大值 maxLeft 和右半部分的最小值 minRight。
    如果 maxLeft 小于等于 minRight，那么我们就找到了合适的划分位置，可以根据数组的总长度是奇数还是偶数来返回中位数。

下面是一个示意图，帮助理解整个过程：

nums1: 1  3 | 8  9
nums2: 2  7  | 10 11 12

在这个例子中，m = 4, n = 5。我们需要找到在 nums1 中的位置 i，
使得 nums1(0) -> nums1(i-1)
和 nums2(0) -> nums2(j-1) 组成的所有元素合并后能够排
在整个合并数组的左半部分。

初始时，我们设置 left = 0, right = 4，然后进行二分查找：
- 第一轮迭代，
i = 2，j = (4 + 5 + 1) / 2 - 2 = 4。
此时
nums1(0) -> nums1(1)
和 nums2(0) -> nums2(3) 组成的所有元素合并后为
[1, 2, 3, 7]，最大值为 3，右半部分最小值为 8。因为 3 <= 8，所以我们找到了合适的划分位置。
- 如果总长度为奇数，中位数为 maxLeft，即 3。

这就是找到两个有序数组的中位数的算法原理。希朿这个解释有帮助！