# O(log(min(m, n, k))) solution with binary search

• It's similar to @StefanPochmann's solution, but more generic and straightforward. Its goal is to find the first element in `nums1` meeting `max(nums1[p], nums2[k-p-2]) <= min(nums1[p+1], nums2[k-p-1])`.

``````class Solution(object):
def get(self, nums, p):
if p < 0:
return float('-inf')

if p >= len(nums):
return float('inf')

return nums[p]

def meeting(self, nums1, nums2, p1, p2):
return max(self.get(nums1, p1), self.get(nums2, p2)) <= min(
self.get(nums1, p1 + 1), self.get(nums2, p2 + 1))

def findKth(self, nums1, nums2, k):
low, high = 0, min(k, len(nums1)) - 1

while low <= high:
p1 = low + high >> 1
p2 = k - p1 - 2

# if it's the first element in nums1 meeting
# max(nums1[p], nums2[k-p-2]) <= min(nums1[p+1], nums2[k-p-1])
if self.meeting(nums1, nums2, p1, p2) and (
p1 == 0 or not self.meeting(nums1, nums2, p1-1, p2+1)):
return max(nums1[p1], self.get(nums2, p2))

if self.get(nums2, p2) > self.get(nums1, p1 + 1):
low = p1 + 1
else:
high = p1 - 1

return nums2[k - 1]

def findMedianSortedArrays(self, nums1, nums2):
m, n = map(len, (nums1, nums2))
if m > n:
return self.findMedianSortedArrays(nums2, nums1)

half = m + n >> 1

if (m + n) & 1:
return self.findKth(nums1, nums2, half + 1)

return (
self.findKth(nums1, nums2, half) +
self.findKth(nums1, nums2, half + 1)
) / 2.0
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.