本篇文章是对leetcode中Median Of Two Sorted Arrays解法的整理。
二分查找
在大家读题的时候不知有没有注意两个小细节“O(log(m+n))”和“Sorted Arrays”。经常刷题的同学可能很容易想到这个不就是二分查找吗。所以我们撇开这题不谈，先看看二分查找。
给定一个有序数组a = [1,3,5,7,9,10,11,13,14,15]，如果快速找到数字11的位置。
如果确定是长度很短的数组，我建议大家直接遍历就行了。但是在项目中这么理想的情况很少存在，我们经常需要处理长度特别长的数组，这时候遍历可能就有点吃不消了。于是一种优化的方法自然成了我们追求的目标，这里给出二分查找的方法。
上面给出的数组是有序的，那么如果把数组在中间一分为二，那是不是意味着我们只需要对左侧数组的最大值（最后一个数字）和右侧数组的最小值（第一个数组）比较，就可以判断目标值11在左半边还是右半边。
采用相同的方法在确定的小数组中继续一分为二并判断，直到找到目标值。
这就是二分查找，来张图演示一下：
Golang代码（非递归）：
func BinarySearch(arr []int, target int)(index int) {
leftIndex, rightIndex := 0, len(arr) - 1
for {
if leftIndex > rightIndex { // 未找到的退出条件
index = -1
break
}
middleIndex := (leftIndex + rightIndex) / 2
if arr[middleIndex] == target { // 找到的退出条件
index = middleIndex
break
} else if arr[middleIndex] > target { //取左侧一半数组
rightIndex = middleIndex - 1
} else { //取右侧一半的数组
leftIndex = middleIndex + 1
}
}
return
}
Golang代码（递归）：
func BinarySearch(arr []int, target int)(index int) {
leftIndex, rightIndex := 0, len(arr) - 1
return recursive(arr, leftIndex, rightIndex, target)
}
func recursive(arr []int, leftIndex, rightIndex, target int) int {
if leftIndex > rightIndex { // 未找到的退出条件
return -1
}
middleIndex := (leftIndex + rightIndex) / 2
if arr[middleIndex] == target { // 找到的退出条件
return middleIndex
} else if arr[middleIndex] > target { //取左侧一半数组
return recursive(arr, leftIndex, middleIndex - 1, target)
} else { //取右侧一半的数组
return recursive(arr, middleIndex + 1, rightIndex, target)
}
}
测试：
func main() {
arr := []int{1,3,5,6,9,10,11,13,14,15}
target := 7
fmt.Println(BinarySearch(arr, target))
}
解题思路
从题目中我们可以看出核心问题是寻找两个数组中第K个数，K为两个数组中间的一个（数组之和为奇数）或两个数（数组之后为偶数），即：
我们以下面一组case为例：
我们需要找到第7和第8个数，求平均。这里我们以第7个数为例进行说明。
首先我们先查找k/2=7/2=3个数据，比较两个数组的第三个元素的大小，我们发现5 < 8，于是我们删除第一个数组的前三个元素。
这里可能有人会问为什么删除第一个数组？因为我们需要保证删除的数据尽可能小，删除了5之后我们可以保证剩余数组中>=5的数的数量会大于整体长度的一半。在这个例子中大于等于5的元素的数量可以确定至少有(9+5)-3-2=9个，其中3是nums1中删除的元素数，2是nums中小于8的元素数。这样可以保证目标值不会被删除。
删除3个元素后，问题变成了寻找第k=7-3=4个元素。采用同样的方式：
我们删除4的一半个元素，即删除nums2中前2个元素。继续采用同样的方法删除剩余的2个元素中的一半：
当k=1时，我们只需要取两个数组第一个元素中较小的元素即可。
同时，我们需要注意两种边界问题：
- 当其中一个数组长度为0时，我们可以直接在另一个数组中获取目标值。
- 当其中一个数组长度小于k/2时，我们可以比较这个数组的最后一个元素。
源代码（Golang）
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
if (len(nums1) + len(nums2)) % 2 == 0 {
return float64(
findKth(nums1, nums2, (len(nums1) + len(nums2)) / 2) +
findKth(nums1, nums2, (len(nums1) + len(nums2)) / 2 + 1)) / 2.0
}
return float64(findKth(nums1, nums2, (len(nums1) + len(nums2)) / 2 + 1))
}
func findKth(nums1, nums2 []int, k int) int {
if len(nums1) == 0 {
return nums2[k - 1]
}
if len(nums2) == 0 {
return nums1[k - 1]
}
if k == 1 {
return min(nums1[0], nums2[0])
}
var num1 int
var num2 int
var to1 int
var to2 int
if k / 2 > len(nums1) {
num1 = nums1[len(nums1) - 1]
to1 = len(nums1)
} else {
num1 = nums1[k / 2 - 1]
to1 = k / 2
}
if k / 2 > len(nums2) {
num2 = nums2[len(nums2) - 1]
to2 = len(nums2)
} else {
num2 = nums2[k / 2 - 1]
to2 = k / 2
}
if num1 > num2 {
return findKth(nums1, nums2[to2:], k - to2)
}
return findKth(nums1[to1:], nums2, k - to1)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
有疑问加站长微信联系（非本文作者）
