4. 寻找两个正序数组的中位数

本题求两个数组求中位数,并且要求Log复杂度,那么必然用到二分法,我们就要考虑怎么比较;

  1. 本题使用求两数组中第k小元素的辅助函数,使得,sumLens=7 时返回 get_k(4) , sumLens=8 时返回 get_k(4) ,get_k(5) ,由此可知,目前为止我们对于get_k的传参k没有考虑index 

  2.  get_k的核心思想就是,哪个数组中位数小,就把该数组左边元素去掉,更新该数组的起始index,并更新k

  3. get_k函数的跳出条件有

    1. 某数组 index 更新到 len(num)了,即该数组元素全被丢弃;则直接返回另一数组第k小元素

    2. k = 1 返回两数组最小值

原文地址:https://www.cnblogs.com/ChevisZhang/p/14059887.html