4.md

4 Median of Two Sorted Arrays

Description

link

---

General

Find k_th position in two sorted arrays

---

Solution : Binary Search

Make sure lenB >= lenA

half, pa, pb = int(k / 2), min(half, lenA), k - pa

every time find half of k numbers which is smaller than k in nums1 and nums2, contrast the number at pa and pb (pa will be lenA if lenA < half)

• nums1[pa - 1] <= nums2[pb - 1] : the nums1[:pa] is smaller than k
• nums1[pa - 1] > nums2[pb - 1] : the nums2[:pb] is smaller than k

notice the border of lenA == 0 and k == 1

---

Code

Complexity T : O(PGK) M : O(GP)

    def findKth(self, nums1, nums2, k):
        k = int(k)
        lenA = len(nums1)
        lenB = len(nums2)
        
        if (lenA > lenB):
            return self.findKth(nums2, nums1, k)
        if lenA == 0:
            return nums2[k - 1]
        if k == 1:
            return min(nums1[0],nums2[0])
        
        half = int(k / 2); pa = min(half, lenA)
        pb = k - pa
        
        if nums1[pa - 1] <= nums2[pb - 1]:
            return self.findKth(nums1[pa:], nums2, pb)
        else:
            return self.findKth(nums1, nums2[pb:], pa)