关于二分查找:学习二分法的完美例题-leetcode-4-寻找两个正序数组的中位数

题目

合并有序数组间接返回中位数

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {    var nums3 []int    var a,b int    //合并数组    for a<len(nums1)&&b<len(nums2){        if nums1[a]<nums2[b]{            nums3=append(nums3,nums1[a])            a++        }else {            nums3=append(nums3,nums2[b])            b++        }    }    if a==len(nums1){        nums3=append(nums3,nums2[b:len(nums2)]...)    }else{        nums3=append(nums3,nums1[a:len(nums1)]...)    }    //取中位数    if len(nums3)%2==1{        return float64(nums3[len(nums3)/2])    }else{        return (float64(nums3[len(nums3)/2-1])+float64(nums3[len(nums3)/2]))/2    }}

复杂度
工夫O（m+n）
空间O（1）

合并数组应用了太多工夫，将其优化为log


因为两个数组都为有序数组，在指标数字之前的数都必然小于它，这就容许咱们进行疾速的排除
定义i，j两个指针，每次排除k/2个必然不是中位数的数，并将指针前移
直到非凡状况找到第k个数

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {    //find (m+n+1)/2 and (m+n+2)/2    m:=len(nums1)    n:=len(nums2)    res1:=getKthElement(nums1,nums2,(m+n+2)/2)    res2:=getKthElement(nums1,nums2,(m+n+1)/2)    return (float64(res1)+float64(res2))/2}func getKthElement(nums1 []int, nums2 []int, k int)int{    var index1,index2 int    for {        //如果一个数组已被排查完，间接返回另一个数组的第k个元素        if index1 == len(nums1) {            return nums2[index2 + k - 1]        }        if index2 == len(nums2) {            return nums1[index1 + k - 1]        }        //如果要找最小的元素，则只有两种可能性，间接比拟找到后果        if k == 1 {            return min(nums1[index1], nums2[index2])        }        //更新排除的数k/2，实现比拟，排除小于k的数，k值减小        half := k/2        newIndex1 := min(index1 + half, len(nums1)) - 1        newIndex2 := min(index2 + half, len(nums2)) - 1        pivot1, pivot2 := nums1[newIndex1], nums2[newIndex2]        if pivot1 <= pivot2 {            k -= (newIndex1 - index1 + 1)            index1 = newIndex1 + 1        } else {            k -= (newIndex2 - index2 + 1)            index2 = newIndex2 + 1        }    }}func min(x, y int) int {    if x < y {        return x    }    return y}