# leetcode 4 寻找两个正序数组的中位数
## 分析
这题要求时间复杂log(m+n),所以要想达到这个目标,自然是 二分查找
可以将题目理解为 两个正序数组的第K大数
```go
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
total := len(nums1) + len(nums2)
if total % 2 == 0 {
// 偶数长度,取中间两个数
left := findKthNumber(nums1, 0, nums2, 0, total / 2)
right := findKthNumber(nums1, 0, nums2, 0, total / 2 + 1)
return float64(left + right) / 2
} else {
// 奇数长度,取中数
return float64(findKthNumber(nums1, 0, nums2, 0, total / 2 + 1))
}
}
// 从nums1[i:] 和 nums2[j:]之间找到第k大数
func findKthNumber(nums1 []int, i int, nums2 []int, j int, k int) int {
// 提前预处理,默认nums1待处理长度小于nums2
if len(nums1) - i > len(nums2) - j {
return findKthNumber(nums2, j, nums1, i, k)
}
// 边界场景1
if len(nums1) == i {
return nums2[j+k-1]
}
// 边界场景2
if k == 1 {
return min(nums1[i], nums2[j])
}
si := min(i + k / 2, len(nums1))
sj := j + k / 2
// 二分
if nums1[si-1] > nums2[sj-1] {
return findKthNumber(nums1, i, nums2, sj, k - k / 2)
} else {
return findKthNumber(nums1, si, nums2, j, k - (si - i))
}
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
```
有疑问加站长微信联系(非本文作者))