题解 |二分查找|#在两个长度相等的排序数组中找到上中位数#

package main

//方法二：二分查找
// 时间复杂度度要求为O(logN)，很容易就想到了二分查找。
// 算法是思路为，先定位到两个数组的中位数，比较此时两个中位数对应的数的大小，再根据结果去进行调整，
// 以数组1不超出范围为循环条件，每次比较区间范围的中位数的大小，将left1和left2这两个指针始终指向可能的中位数的位置，因为数组是从小到大进行排序的。
func findMedianinTwoSortedAray(arr1 []int, arr2 []int) int {
	len := len(arr1)
	if len == 1 {
		return min(arr1[0], arr2[0])
	}
	l1, r1, l2, r2 := 0, len-1, 0, len-1
	mid1, mid2, even := 0, 0, 0 //用于记录每轮中间的指针和当前子区间是否为偶数
	for l1 < r1 {
		even = (r1 - l1) % 2  //区间长度偶数为1，奇数为0
		mid1 = (l1 + r1) >> 1 //求第一个数组中间指针
		mid2 = (l2 + r2) >> 1 //求第二个数组中间指针
		if arr1[mid1] == arr2[mid2] {
			return arr1[mid1] //若是子区间中间值相等，则直接返回数值
		} else if arr1[mid1] < arr2[mid2] { //当一个子区间的中值小于另一个区间的中值时
			l1 = mid1 + even //我们取较小中值区间的右半部分，注意长度为偶数的子区间中值后一位才是右半部分的起点
			r2 = mid2        //取较大中值区间的左半部分
		} else { //以下同理
			l2 = mid2 + even
			r1 = mid1
		}
	}
    return min(arr1[l1], arr2[l2]); //此时两个指针指向排序后中间的两个数，只需返回其中较小的数
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}