在两个排序数组中找第k小的数

题目描述
给定两个有序数组arr1和arr2，再给定一个整数K，返回所有数中第K小的数。
[要求]
如果arr1的长度为N，arr2的长度为M，时间复杂度请达到O(\log(\min{N, M}))O(log(minN,M))，额外空间复杂度O(1)O(1)。
输入描述:
第一行三个整数N, M, K分别表示数组arr1, arr2的大小，以及需要询问的数
接下来一行N个整数，表示arr1内的元素
再接下来一行M个整数，表示arr2内的元素
输出描述:
输出一个整数表示答案

我们以下列数组为例子：

arr1={1,2,3,4,5}
arr2={3,4,5}
k=4

我们希望找到第4小的数3，在两个数组中，有三个数字1、2、3小于等于3，所以我们可以把整个数组分成两部分：第一部分包括arr1[0]~arr1[2],arr2[0]，其它元素在第二部分，我们定义这两个部分为left和right，left在两个数组中的边界下标为2和0（arr1[2]和arr2[0]）。

可以发现，left当中有k个元素，并且left当中所有的元素小于等于right中的元素。在这种情况下，left当中的最大值就是第k小的元素。所以题目可以转化为：保证left当中有k个元素并且left当中的元素全部小于等于right当中的元素，为了满足上述要求，必须找到left的边界下标。

当我们选定一个arr1下标的时候，为了保证left当中包含k个元素，arr2的下标也就随之确定了。如果不满足left<=right，我们可以根据特定的条件判断，调整下标的位置。

我们可以通过二分查找的方式确定arr1的下标，在上述例子中，首先找到arr1的中点下标2，由于left当中要有4个元素，所以arr2的下标为0，此时left<=right，所以left中最大值就是第k小的元素。

我们在以k=7为例，首先在arr1当中，l=0，r=4，找到arr1的中点下标2，由于left当中要有7个元素，arr1提供了3个元素，arr2必须提供4个元素，没有办法实现，此时说明arr1提供的元素太少了，所以l=2+1=3，继续二分查找left和right的分割点。随后确定arr1的下标3，对应的arr2的下标为2，此时left当中的元素小于等于right当中的元素，所以结果为left当中最大值5.

我们可以确定如下判断规则：

假设left当中，arr1最后一个元素下标是i，arr2最后一个元素下标为j，如果：
1、arr1[i]<=arr2[j+1]，并且arr2[j]<=arr1[i+1],说明left里面的元素小于等于right当中的元素，left最大值是第k小的元素。
2、arr1[i]>arr2[j+1]，left当中arr1的边界需要左移动，所以在arr1[i]以左继续二分查找
3、arr2[j]>arr1[i+1]，left当中arr1的边界需要右移动，所以在arr1[i]以右继续二分查找

这里还需要注意以下边界条件，因为j+1和i+1都是有可能越界的。另外，在划分left和right的过程中，也存在一种边界情况：arr1和arr2的下标可以为-1，例如上面的那个例子中，如果left当中arr1的下标为1，arr2的下标为-1，此时left当中只有arr1的两个元素1，2，此时找到的是第二大的元素。所以在二分查找的过程中，初始l=-1,r=len(arr1)-1。

注意我们的核心思想是要让left中所有元素<=right中所有元素，所以当left中arr1边界是arr1最后一个元素的时候，arr1[i+1]是不需要判断的，同理当left中arr2的边界是最后一个元素的时候不需要判断arr2[j+1]。

总的求解代码如下，其中n为arr1长度，m为arr2长度，solve()函数返回第k大的元素

package main
import(
    "bufio"
    "os"
    "strconv"
    //"fmt"
)
var in,out=bufio.NewReader(os.Stdin),bufio.NewWriter(os.Stdout)
var n,m,k int
var arr1,arr2 []int
func read() int{
    ret:=0
    for c,_:=in.ReadByte();c>='0' && c<='9';c,_=in.ReadByte(){
        ret=(ret*10)+int(c-'0')
    }
    return ret
}
func main(){
    n,m,k=read(),read(),read()
    arr1,arr2=make([]int,n),make([]int,m)
    for i:=0;i<n;i++{
        arr1[i]=read()
    }
    for i:=0;i<m;i++{
        arr2[i]=read()
    }
    result:=solve()
    out.WriteString(strconv.Itoa(result))
    out.WriteByte('\n')
    out.Flush()
    return
}
func solve() int {
    if k==1{
        return min(arr1[0],arr2[0])
    }else if k==n+m{
        return max(arr1[n-1],arr2[m-1])
    }
    
    for l,r:=-1,n-1;l<=r;{
        mid:=(l+r)>>1
        arr2Point:=k-(mid+1)-1//left当中，arr2最后一个元素下标
        //fmt.Println("l=",l,"r=",r,"mid=",mid,"arr2Point=",arr2Point)
        if arr2Point<(-1){
            r=mid-1
        }else if arr2Point>=m{
            l=mid+1
        }else{
            var leftmax,rightmin int
            if mid==-1{
                leftmax=arr2[arr2Point]
            }else if arr2Point==-1{
                leftmax=arr1[mid]
            }else{
                leftmax=max(arr1[mid],arr2[arr2Point])
            }
            if mid==n-1{
                rightmin=arr2[arr2Point+1]
            }else if arr2Point==m-1{
                rightmin=arr1[mid+1]
            }else{
                rightmin=min(arr1[mid+1],arr2[arr2Point+1])
            }
            
            //fmt.Println("leftmax=",leftmax,"rightmin=",rightmin)
            if leftmax<=rightmin{
                return leftmax
            }else if arr2Point!=-1 && mid+1!=n &&  
            arr2[arr2Point]>arr1[mid+1]{
                l=mid+1
            }else if mid!=-1 && arr2Point+1!=m &&
            arr1[mid]>arr2[arr2Point+1]{
                r=mid-1
            }
        }
    }
    return 0
}
func max(a,b int) int{
    if a>b{
        return a
    }else{
        return b
    }
}
func min(a,b int) int{
    if a<b{
        return a
    }else{
        return b
    }
}