Given two sorted arrays array1 and array2 of size m and n respectively. Find the median of the two sorted arrays.
Example 1:
Input:
m = 3, n = 4
array1[] = {1,5,9}
array2[] = {2,3,6,7}
Output: 5
Explanation: The middle element for
{1,2,3,5,6,7,9} is 5
Example 2:
Input:
m = 2, n = 4
array1[] = {4,6}
array2[] = {1,2,3,5}
Output: 3.5
Your Task:
The task is to complete the function MedianOfArrays() that takes array1 and array2 as input and returns their median. 
Can you solve the problem in expected time complexity?
Expected Time Complexity: O(min(log n, log m)).
Expected Auxiliary Space: O((n+m)/2).
Constraints: 
0 ≤ m,n ≤ 10^{6}
1 ≤ array1[i], array2[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def MedianOfArrays(self, array1, array2):

            #code here

Solutions:
class Solution:

	def MedianOfArrays(self, array1, array2):
		(n1, n2) = (len(array1), len(array2))
		total = n1 + n2
		half = total // 2
		if n2 < n1:
			return self.MedianOfArrays(array2, array1)
		(l, r) = (0, n1 - 1)
		while True:
			i = (r + l) // 2
			j = half - i - 2
			left_1 = array1[i] if i >= 0 else float('-inf')
			right_1 = array1[i + 1] if i + 1 < n1 else float('inf')
			left_2 = array2[j] if j >= 0 else float('-inf')
			right_2 = array2[j + 1] if j + 1 < n2 else float('inf')
			if left_1 <= right_2 and left_2 <= right_1:
				if total % 2 == 0:
					sum = max(left_1, left_2) + min(right_1, right_2)
					if sum % 2 == 0:
						return sum // 2
					return sum / 2
				else:
					return min(right_1, right_2)
			elif left_1 > right_2:
				r = i - 1
			else:
				l = i + 1


class Solution:

	def MedianOfArrays(self, array1, array2):
		b = []
		for i in array1:
			b.append(i)
		for j in array2:
			b.append(j)
		b.sort()
		n = len(b)
		m = n // 2
		med = (b[m] + b[m - 1]) / 2
		if n % 2 == 0:
			if med % 1 == 0:
				med = int(med)
			else:
				med = float(med)
			return med
		else:
			return int(b[m])


class Solution:

	def MedianOfArrays(self, array1, array2):
		arr = array1 + array2
		arr.sort()
		n = len(arr)
		if n % 2 == 0:
			median = (arr[n // 2 - 1] + arr[n // 2]) / 2
			if median == float(median // 1):
				median = int(median)
		else:
			median = arr[n // 2]
		return median


import math

class Solution:

	def MedianOfArrays(self, array1, array2):
		(i, j) = (0, 0)
		(a1, a2) = (len(array1), len(array2))
		arr3 = []
		while i < a1 and j < a2:
			if array1[i] < array2[j]:
				arr3.append(array1[i])
				i += 1
			else:
				arr3.append(array2[j])
				j += 1
		while i < a1:
			arr3.append(array1[i])
			i += 1
		while j < a2:
			arr3.append(array2[j])
			j += 1
		if (a1 + a2) % 2 != 0:
			return arr3[(a1 + a2) // 2]
		else:
			temp1 = arr3[(a1 + a2) // 2]
			temp2 = arr3[(a1 + a2) // 2 - 1]
			ans = str((temp1 + temp2) / 2).split('.')
			if ans[-1] != '0':
				return (temp1 + temp2) / 2
			else:
				return (temp1 + temp2) // 2


class Solution:

	def MedianOfArrays(self, array1, array2):
		l = len(array1) + len(array2)
		a = array1 + array2
		a.sort()
		if l % 2 != 0:
			return a[l // 2]
		elif (a[l // 2] + a[l // 2 - 1]) % 2 == 0:
			return (a[l // 2] + a[l // 2 - 1]) // 2
		else:
			return (a[l // 2] + a[l // 2 - 1]) / 2


class Solution:

	def MedianOfArrays(self, a, b):
		ans = []
		i = 0
		j = 0
		n = len(a)
		m = len(b)
		if n == 1 and m == 1:
			return (a[0] + b[0]) // 2
		while i < n and j < m:
			if a[i] < b[j]:
				ans.append(a[i])
				i += 1
			else:
				ans.append(b[j])
				j += 1
		while i < n:
			ans.append(a[i])
			i += 1
		while j < m:
			ans.append(b[j])
			j += 1
		if (n + m) % 2 == 0:
			x = (n + m) // 2 - 1
			y = (n + m) // 2
			z = (ans[x] + ans[y]) / 2
			if z == int(z):
				return int(z)
			return z
		else:
			z = (m + n + 1) // 2 - 1
			return ans[z]


class Solution:

	def median(self, merge, mid, even):
		if even:
			if (merge[mid] + merge[mid - 1]) % 2 == 0:
				return (merge[mid] + merge[mid - 1]) // 2
			else:
				return (merge[mid] + merge[mid - 1]) / 2
		else:
			return merge[mid]

	def MedianOfArrays(self, array1, array2):
		merge = []
		n = len(array1)
		m = len(array2)
		(i, j) = (0, 0)
		even = (n + m) % 2 == 0
		mid = (n + m) // 2
		k = 0
		while i < n and j < m:
			if array1[i] < array2[j]:
				merge.append(array1[i])
				i += 1
			else:
				merge.append(array2[j])
				j += 1
			k += 1
			if k - 1 == mid:
				return self.median(merge, k - 1, even)
		while i < n:
			merge.append(array1[i])
			i += 1
			k += 1
			if k - 1 == mid:
				return self.median(merge, k - 1, even)
		while j < m:
			merge.append(array2[j])
			j += 1
			k += 1
			if k - 1 == mid:
				return self.median(merge, k - 1, even)


class Solution:

	def MedianOfArrays(self, array1, array2):
		merge = []
		n = len(array1)
		m = len(array2)
		(i, j) = (0, 0)
		while i < n and j < m:
			if array1[i] < array2[j]:
				merge.append(array1[i])
				i += 1
			else:
				merge.append(array2[j])
				j += 1
		while i < n:
			merge.append(array1[i])
			i += 1
		while j < m:
			merge.append(array2[j])
			j += 1
		if (n + m) % 2 == 0:
			nm = (n + m) // 2
			if (merge[nm] + merge[nm - 1]) % 2 == 0:
				return (merge[nm] + merge[nm - 1]) // 2
			else:
				return (merge[nm] + merge[nm - 1]) / 2
		else:
			return merge[(n + m) // 2]


class Solution:

	def MedianOfArrays(self, array1, array2):
		array3 = []
		array3 = array1 + array2
		array3.sort()
		a = len(array3)
		if a % 2 == 0:
			len1 = int((a - 1) / 2)
			ans = (array3[len1] + array3[len1 + 1]) / 2
			if int(ans) == ans:
				return int(ans)
			return ans
		else:
			len1 = int((a - 1) / 2)
			return array3[len1]


class Solution:

	def MedianOfArrays(self, array1, array2):
		array1.sort()
		array2.sort()
		arr = array1 + array2
		arr.sort()
		L = len(arr)
		if L % 2 != 0:
			i = L // 2
			return arr[i]
		else:
			i = (arr[L // 2 - 1] + arr[L // 2]) / 2
			if i - int(i) > 0:
				return i
			else:
				return int(i)


class Solution:

	def MedianOfArrays(self, array1, array2):
		array1 = array1 + array2
		array1.sort()
		n = len(array1)
		if len(array1) % 2 != 0:
			return array1[n // 2]
		else:
			ans = (array1[n // 2] + array1[n // 2 - 1]) / 2
			if ans == int(ans):
				return int(ans)
			else:
				return ans


import sys

class Solution:

	def MedianOfArrays(self, array1, array2):
		n = len(array1)
		m = len(array2)
		if n > m:
			return self.MedianOfArrays(array2, array1)
		total_len = m + n
		left = 0
		right = n
		result = 0
		while left <= right:
			cut1 = left + (right - left) // 2
			cut2 = total_len // 2 - cut1
			l1 = -sys.maxsize if cut1 == 0 else array1[cut1 - 1]
			l2 = -sys.maxsize if cut2 == 0 else array2[cut2 - 1]
			r1 = sys.maxsize if cut1 == n else array1[cut1]
			r2 = sys.maxsize if cut2 == m else array2[cut2]
			if l1 <= r2 and l2 <= r1:
				if total_len % 2 != 0:
					result = min(r1, r2)
					break
				else:
					result = (max(l1, l2) + min(r1, r2)) / 2
			if l1 > r2:
				right = cut1 - 1
			else:
				left = cut1 + 1
		return int(result) if result / int(result) == 1 else result


class Solution:

	def MedianOfArrays(self, array1, array2):
		n = len(array1)
		m = len(array2)
		i = n - 1
		j = 0
		while i >= 0 and j < m:
			if array1[i] >= array2[j]:
				(array1[i], array2[j]) = (array2[j], array1[i])
				i -= 1
				j += 1
			else:
				break
		array1.sort()
		array2.sort()
		mid = int((n + m) / 2)
		res = array1 + array2
		if (m + n) % 2 == 0:
			r = (res[mid - 1] + res[mid]) / 2
			if r - int(r) == 0:
				return int(r)
			return r
		return res[mid]


class Solution:

	def MedianOfArrays(self, array1, array2):
		arr = array1 + array2
		arr.sort()
		length = len(arr)
		z = length // 2
		if length % 2 == 1:
			return arr[z]
		elif length % 2 == 0:
			xy = (arr[z - 1] + arr[z]) / 2
			if xy.is_integer():
				return int(xy)
			else:
				return xy


class Solution:

	def MedianOfArrays(self, array1, array2):
		v = array1 + array2
		v.sort()
		a = len(v)
		if len(v) % 2 == 1:
			return v[a // 2]
		else:
			n = a // 2
			result = (v[n] + v[n - 1]) / 2
			if result.is_integer():
				return int(result)
			else:
				return result


class Solution:

	def MedianOfArrays(self, array1, array2):
		arr3 = arr1 + arr2
		arr3.sort()
		l = len(arr3)
		if len(arr3) % 2 == 1:
			return arr3[l // 2]
		else:
			b = len(arr3) // 2
			result = (arr3[b] + arr3[b - 1]) / 2
			if result.is_integer():
				return int(result)
			else:
				return result


class Solution:

	def MedianOfArrays(self, array1, array2):
		a3 = array1 + array2
		a3.sort()
		l = len(a3)
		if l % 2 == 1:
			return a3[l // 2]
		else:
			azif = (a3[l // 2] + a3[l // 2 - 1]) / 2
			if azif.is_integer():
				return int(azif)
			else:
				return azif


class Solution:

	def MedianOfArrays(self, array1, array2):
		a3 = array1 + array2
		a3.sort()
		l = len(a3)
		if len(a3) % 2 == 1:
			a = len(a3) // 2
			return a3[a]
		else:
			b = len(a3) // 2
			result = (a3[b] + a3[b - 1]) / 2
			if result.is_integer():
				return int(result)
			else:
				return result


class Solution:

	def MedianOfArrays(self, array1, array2):
		merged = sorted(arr1 + arr2)
		n = len(merged)
		if n % 2 != 0:
			return merged[n // 2]
		else:
			A = merged[n // 2 - 1] + merged[n // 2]
			if A % 2 == 0:
				return A // 2
			else:
				return A / 2


class Solution:

	def MedianOfArrays(self, array1, array2):
		l = array1 + array2
		l.sort()
		n = len(l)
		if n % 2 == 0:
			x = l[int((n - 1) / 2)]
			y = l[int(n / 2)]
			if (x + y) % 2 == 0:
				return (x + y) // 2
			else:
				return (x + y) / 2
		else:
			return l[n // 2]


class Solution:

	def MedianOfArrays(self, array1, array2):
		output = array1 + array2
		output.sort()
		o = len(output)
		if o % 2 == 1:
			return output[o // 2]
		else:
			r = o // 2 - 1
			ret1 = output[r]
			ret2 = output[r + 1]
			out = (ret2 + ret1) / 2
			if out.is_integer():
				return int(out)
			else:
				return out


class Solution:

	def MedianOfArrays(self, array1, array2):
		l = []
		s = 0
		for i in array1:
			l.append(i)
		for j in array2:
			l.append(j)
		l.sort()
		n = len(l)
		if n % 2 == 0:
			d = n // 2
			v = l[d] + l[d - 1]
			s = v / 2
			if s.is_integer():
				return int(s)
			else:
				return s
		else:
			r = n // 2
			t = l[r]
			return t


class Solution:

	def MedianOfArrays(self, array1, array2):
		arr = array1 + array2
		arr.sort()
		l = len(arr)
		if l % 2 == 0:
			med = arr[l // 2] + arr[l // 2 - 1]
			if med / 2 > med // 2:
				return med / 2
			return med // 2
		return arr[l // 2]


class Solution:

	def MedianOfArrays(self, array1, array2):
		arr = sorted(array1) + sorted(array2)
		arr.sort()
		n = len(arr)
		if n % 2 == 0:
			z = n // 2
			res = (arr[z] + arr[z - 1]) / 2
			if int(res) == res:
				return int(res)
			else:
				return res
		return arr[n // 2]


class Solution:

	def MedianOfArrays(self, array1, array2):
		if len(array1) > len(array2):
			return self.MedianOfArrays(array2, array1)
		(m, n) = (len(array1), len(array2))
		(low, high) = (0, m)
		while low <= high:
			cut1 = (low + high) // 2
			cut2 = (m + n + 1) // 2 - cut1
			l1 = array1[cut1 - 1] if cut1 != 0 else -float('inf')
			l2 = array2[cut2 - 1] if cut2 != 0 else -float('inf')
			r1 = array1[cut1] if cut1 != m else float('inf')
			r2 = array2[cut2] if cut2 != n else float('inf')
			if l1 <= r2 and l2 <= r1:
				if (n + m) % 2 == 0:
					val = (max(l1, l2) + min(r1, r2)) / 2
					if val == int(val):
						return int(val)
					return val
				else:
					return max(l1, l2)
			elif l1 > r2:
				high = cut1 - 1
			else:
				low = cut1 + 1
		return 0


class Solution:

	def MedianOfArrays(self, array1, array2):
		x = array1 + array2
		x.sort()
		l = len(x)
		if l % 2 == 0:
			a = (x[l // 2] + x[l // 2 - 1]) / 2
			if a % 1 != 0:
				pass
			else:
				a = int(a)
		else:
			a = x[l // 2]
		return a


class Solution:

	def MedianOfArrays(self, array1, array2):
		(m, n) = (len(array1), len(array2))
		if m > n:
			(array1, array2, m, n) = (array2, array1, n, m)
		(low, high) = (0, m)
		while low <= high:
			partitionX = (low + high) // 2
			partitionY = (m + n + 1) // 2 - partitionX
			maxLeftX = float('-inf') if partitionX == 0 else array1[partitionX - 1]
			minRightX = float('inf') if partitionX == m else array1[partitionX]
			maxLeftY = float('-inf') if partitionY == 0 else array2[partitionY - 1]
			minRightY = float('inf') if partitionY == n else array2[partitionY]
			if maxLeftX <= minRightY and maxLeftY <= minRightX:
				if (m + n) % 2 == 0:
					median = (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
					return int(median) if median.is_integer() else median
				else:
					return max(maxLeftX, maxLeftY)
			elif maxLeftX > minRightY:
				high = partitionX - 1
			else:
				low = partitionX + 1


class Solution:

	def MedianOfArrays(self, array1, array2):
		t = sorted(array1 + array2)
		if len(t) % 2 == 0:
			return str((t[len(t) // 2] + t[len(t) // 2 - 1]) / 2).rstrip('.0')
			pass
		else:
			return t[len(t) // 2]


class Solution:

	def MedianOfArrays(self, array1, array2):
		newarr = array1 + array2
		newarr.sort()
		n = len(newarr)
		if n % 2 != 0:
			return newarr[int(n / 2)]
		else:
			v = (newarr[int(n / 2)] + newarr[int(n / 2) - 1]) / 2
			k = int(v)
			if v == k:
				return k
			else:
				return v


import statistics

class Solution:

	def MedianOfArrays(self, array1, array2):
		l1 = array1 + array2
		v = sorted(l1)
		d = statistics.median(v)
		s = d % 1
		if s > 0.1 and s < 0.9:
			return d
		else:
			return int(d)


class Solution:

	def MedianOfArrays(self, array1, array2):
		v = []
		for i in array1:
			v.append(i)
		for i in array2:
			v.append(i)
		v.sort()
		n = len(v)
		if n % 2 == 0:
			a = int(n / 2) - 1
			k = (v[a] + v[a + 1]) / 2
			if k - int(k) == 0:
				return int(k)
			else:
				return k
		else:
			a = n
			a = int((a - 1) / 2)
			k = v[a]
			if k - int(k) == 0:
				return int(k)
			else:
				return k


class Solution:

	def MedianOfArrays(self, array1, array2):
		v = array1 + array2
		v.sort()
		l = len(v)
		if l % 2 == 1:
			return v[l // 2]
		else:
			if (v[l // 2] + v[l // 2 - 1]) % 2 == 0:
				return (v[l // 2] + v[l // 2 - 1]) // 2
			return (v[l // 2] + v[l // 2 - 1]) / 2


class Solution:

	def MedianOfArrays(self, array1, array2):
		if len(array2) < len(array1):
			return self.MedianOfArrays(array2, array1)
		low = 0
		high = len(array1)
		while low <= high:
			cut1 = (low + high) // 2
			cut2 = (len(array1) + len(array2) + 1) // 2 - cut1
			if cut1 == 0:
				left1 = -214787878
			else:
				left1 = array1[cut1 - 1]
			if cut2 == 0:
				left2 = -214787878
			else:
				left2 = array2[cut2 - 1]
			if cut1 == len(array1):
				right1 = 21478787807079
			else:
				right1 = array1[cut1]
			if cut2 == len(array2):
				right2 = 21478787807079
			else:
				right2 = array2[cut2]
			if left1 <= right2 and left2 <= right1:
				if (len(array1) + len(array2)) % 2 == 0:
					if (max(left1, left2) + min(right1, right2)) % 2 == 0:
						return (max(left1, left2) + min(right1, right2)) // 2
					else:
						return (max(left1, left2) + min(right1, right2)) / 2
				else:
					return max(left1, left2)
			elif left1 > right2:
				high = cut1 - 1
			else:
				low = cut1 + 1
		return 0


class Solution:

	def MedianOfArrays(self, array1, array2):
		array1.extend(array2)
		array1.sort()
		if len(array1) % 2 == 0:
			a = (array1[len(array1) // 2] + array1[len(array1) // 2 - 1]) / 2
			if a == int(a):
				return int(a)
			return a
		else:
			return array1[len(array1) // 2]


class Solution:

	def MedianOfArrays(self, array1, array2):
		l1 = len(array1)
		l2 = len(array2)
		diff = abs(l2 - l1)
		if diff % 2 == 0:
			avg = True
		else:
			avg = False
		if l1 == 1 and l2 == 1:
			if (array1[0] + array2[0]) / 2 > (array1[0] + array2[0]) // 2:
				return (array1[0] + array2[0]) / 2
			return (array1[0] + array2[0]) // 2
		i = 0
		j = 0
		First = True
		count = -1
		arr1 = []
		cond = False
		while i < l1 or j < l2:
			if (cond and i < l1 or l2 == 0) or (i < l1 and array1[i] < array2[j]):
				arr1.append(array1[i])
				i += 1
				if i == l1:
					cond = True
				count += 1
			elif l2 != 0:
				if cond and j < l2 or j < l2:
					arr1.append(array2[j])
					j += 1
					if j == l2:
						cond = True
					count += 1
			if count == (l1 + l2) // 2:
				break
		if not avg:
			return arr1[-1]
		else:
			idiv = (arr1[-1] + arr1[-2]) // 2
			fdiv = (arr1[-1] + arr1[-2]) / 2
			if fdiv > idiv:
				return fdiv
			return idiv


class Solution:

	def MedianOfArrays(self, array1, array2):
		n1 = len(array1)
		n2 = len(array2)
		if n1 > n2:
			return self.MedianOfArrays(array2, array1)
		start = 0
		end = n1
		real_mid = (n1 + n2 + 1) // 2
		while start <= end:
			cut1 = (start + end) // 2
			cut2 = real_mid - cut1
			left1 = array1[cut1 - 1] if cut1 > 0 else float('-inf')
			left2 = array2[cut2 - 1] if cut2 > 0 else float('-inf')
			right1 = array1[cut1] if cut1 < n1 else float('inf')
			right2 = array2[cut2] if cut2 < n2 else float('inf')
			if left1 <= right2 and left2 <= right1:
				if (n1 + n2) % 2 == 0:
					median = (max(left1, left2) + min(right1, right2)) / 2.0
					if median == int(median):
						median = int(median)
				else:
					median = max(left1, left2)
				return median
			elif left1 > right2:
				end = cut1 - 1
			else:
				start = cut1 + 1


class Solution:

	def MedianOfArrays(self, array1, array2):
		n = len(array1)
		m = len(array2)
		if n > m:
			return self.MedianOfArrays(array2, array1)
		start = 0
		end = n
		real_mid = (n + m + 1) // 2
		while start <= end:
			mid = (start + end) // 2
			leftAsize = mid
			leftBsize = real_mid - mid
			left1 = array1[leftAsize - 1] if leftAsize > 0 else float('-inf')
			left2 = array2[leftBsize - 1] if leftBsize > 0 else float('-inf')
			right1 = array1[leftAsize] if leftAsize < n else float('inf')
			right2 = array2[leftBsize] if leftBsize < m else float('inf')
			if left1 <= right2 and left2 <= right1:
				if (n + m) % 2 == 0:
					median = (max(left1, left2) + min(right1, right2)) / 2.0
					if median == int(median):
						median = int(median)
				else:
					median = max(left1, left2)
				return median
			elif left1 > right2:
				end = mid - 1
			else:
				start = mid + 1


class Solution:

	def MedianOfArrays(self, A, B):
		n = len(A)
		m = len(B)
		if n > m:
			return self.MedianOfArrays(B, A)
		start = 0
		end = n
		realmidinmergedarray = (n + m + 1) // 2
		while start <= end:
			mid = (start + end) // 2
			leftAsize = mid
			leftBsize = realmidinmergedarray - mid
			leftA = A[leftAsize - 1] if leftAsize > 0 else float('-inf')
			leftB = B[leftBsize - 1] if leftBsize > 0 else float('-inf')
			rightA = A[leftAsize] if leftAsize < n else float('inf')
			rightB = B[leftBsize] if leftBsize < m else float('inf')
			if leftA <= rightB and leftB <= rightA:
				if (m + n) % 2 == 0:
					median = (max(leftA, leftB) + min(rightA, rightB)) / 2.0
					if median == int(median):
						median = int(median)
					return median
				return max(leftA, leftB)
			elif leftA > rightB:
				end = mid - 1
			else:
				start = mid + 1


class Solution:

	def MedianOfArrays(self, array1, array2):
		m = len(array1)
		n = len(array2)
		if m > n:
			return self.MedianOfArrays(array2, array1)
		mini = -(2 ** 31 - 1)
		maxi = 2 ** 31
		k = m + n + 1 >> 1
		lo = max(0, k - n)
		hi = min(m, k)
		while lo <= hi:
			cut1 = lo + hi >> 1
			cut2 = k - cut1
			l1 = mini if cut1 == 0 else array1[cut1 - 1]
			l2 = mini if cut2 == 0 else array2[cut2 - 1]
			r1 = maxi if cut1 == m else array1[cut1]
			r2 = maxi if cut2 == n else array2[cut2]
			if l1 <= r2 and l2 <= r1:
				if m + n & 1:
					return max(l1, l2)
				else:
					temp = (max(l1, l2) + min(r1, r2)) / 2
					if (max(l1, l2) + min(r1, r2)) % 2:
						return temp
					else:
						return (max(l1, l2) + min(r1, r2)) // 2
			elif l2 > r1:
				lo = cut1 + 1
			else:
				hi = cut1 - 1


class Solution:

	def get_count(self, arrays, mid):
		count = 0
		for arr in arrays:
			count += len([i for i in arr if i <= mid])
		return count

	def MedianOfArrays(self, array1, array2):
		n1 = len(array1)
		n2 = len(array2)
		s = n1 + n2
		pos = []
		if s % 2 == 0:
			pos.append(s // 2)
			pos.append(s // 2 - 1)
		else:
			pos.append(s // 2)
		ans = 0
		for p in pos:
			low = 0
			high = 10 ** 9
			while low <= high:
				mid = low + (high - low) // 2
				count = self.get_count([array1, array2], mid)
				if count <= p:
					low = mid + 1
				else:
					high = mid - 1
			ans += low
		if s % 2 == 0:
			ans = ans / 2
			if ans == int(ans):
				ans = int(ans)
		return ans


import math

class Solution:

	def MedianOfArrays(self, a1, a2):
		i = 0
		j = 0
		median = math.ceil(0.5 * (len(a1) + len(a2)))
		last2 = []
		curr = 1
		if (len(a1) + len(a2)) % 2 == 1:
			while i < len(a1) and j < len(a2):
				if a1[i] < a2[j]:
					if curr == median:
						return a1[i]
					i += 1
				else:
					if curr == median:
						return a2[j]
					j += 1
				curr += 1
			while i < len(a1):
				if curr == median:
					return a1[i]
				i += 1
				curr += 1
			while j < len(a2):
				if curr == median:
					return a2[j]
				j += 1
				curr += 1
		else:
			while i < len(a1) and j < len(a2):
				if len(last2) == 2:
					break
				if a1[i] < a2[j]:
					if curr == median:
						last2.append(a1[i])
					elif curr == median + 1:
						last2.append(a1[i])
					i += 1
					curr += 1
				else:
					if curr == median:
						last2.append(a2[j])
					elif curr == median + 1:
						last2.append(a2[j])
					j += 1
					curr += 1
			while i < len(a1):
				if len(last2) == 2:
					break
				if curr == median:
					last2.append(a1[i])
				elif curr == median + 1:
					last2.append(a1[i])
				i += 1
				curr += 1
			while j < len(a2):
				if len(last2) == 2:
					break
				if curr == median:
					last2.append(a2[j])
				elif curr == median + 1:
					last2.append(a2[j])
				j += 1
				curr += 1
		mean = (last2[0] + last2[1]) / 2.0
		return mean if mean % 1 else int(mean)


class Solution:

	def MedianOfArrays(self, array1, array2):
		new_arr = array1 + array2
		new_arr.sort()
		n = len(new_arr)
		if n % 2 != 0:
			left = 0
			right = n
			mid = (left + right) // 2
			ans = new_arr[mid]
		else:
			left = 0
			right = n // 2
			ans = (new_arr[right] + new_arr[right - 1]) / 2
		new_ans = int(ans)
		if ans > new_ans:
			return ans
		return new_ans


class Solution:

	def MedianOfArrays(self, a1, a2):
		x = a1 + a2
		x.sort()
		y = len(x)
		if y % 2 != 0:
			return x[y // 2]
		else:
			r = (x[y // 2] + x[y // 2 - 1]) / 2
			r1 = (x[y // 2] + x[y // 2 - 1]) // 2
			if r - r1 == 0.0:
				return r1
			else:
				return r


class Solution:

	def MedianOfArrays(self, array1, array2):
		list1 = array1 + array2
		list2 = sorted(list1)
		if len(list2) % 2 != 0:
			return list2[(len(list2) - 1) // 2]
		m = (list2[(len(list2) - 1) // 2] + list2[(len(list2) - 1) // 2 + 1]) / 2
		p = str(m)
		list1 = p.split('.')
		if list1[-1] == '0':
			return int(list1[0])
		return m


class Solution:

	def MedianOfArrays(self, array1, array2):
		arr = array1 + array2
		arr.sort()
		m = len(arr) // 2
		if len(arr) & 1:
			return arr[m]
		else:
			s = arr[m - 1] + arr[m]
			if s % 2:
				return s / 2
			else:
				return s // 2


class Solution:

	def MedianOfArrays(self, array1, array2):
		arr = array1 + array2
		arr.sort()
		a = len(arr)
		if a % 2 != 0:
			return arr[a // 2]
		else:
			k = (arr[a // 2 - 1] + arr[a // 2]) / 2
			a = str(k)
			b = a.index('.')
			if a[b + 1] == '0':
				return int(k)
			else:
				return k


class Solution:

	def MedianOfArrays(self, array1, array2):
		array3 = array1 + array2
		array3.sort()
		n = len(array3)
		if n % 2 != 0:
			return array3[n // 2]
		else:
			median = (array3[n // 2] + array3[n // 2 - 1]) / 2
			if median.is_integer():
				return int(median)
			else:
				return median


class Solution:

	def MedianOfArrays(self, array1, array2):
		for i in array2:
			array1.append(i)
		array1.sort()
		c = len(array1)
		if c % 2 != 0:
			return array1[c // 2]
		else:
			m = array1[c // 2] + array1[c // 2 - 1]
			if m % 2 == 0:
				return m // 2
			return m / 2


class Solution:

	def MedianOfArrays(self, array1, array2):
		array1.extend(array2)
		array1.sort()
		if len(array1) % 2 != 0:
			idx = len(array1) // 2
			return array1[idx]
		else:
			idx = len(array1) // 2
			ele = str((array1[idx - 1] + array1[idx]) / 2)
			idx = ele.index('.')
			if int(ele[idx + 1:]) == 0:
				return int(ele[:idx])
			else:
				return float(ele)


class Solution:

	def MedianOfArrays(self, array1, array2):
		array1[:] = array1[:] + array2[:]
		array1.sort()
		length = len(array1)
		if length % 2 != 0:
			return array1[len(array1) // 2]
		else:
			val = array1[length // 2 - 1] + array1[length // 2]
			if val % 2 == 0:
				return val // 2
			else:
				return val / 2


class Solution:

	def MedianOfArrays(self, array1, array2):
		a = array1 + array2
		a = sorted(a)
		n = len(a)
		if n % 2 != 0:
			d = n // 2
			return a[d]
		else:
			b = n // 2
			c = a[b] + a[b - 1]
			if c % 2 == 0:
				return c // 2
			else:
				return c / 2


class Solution:

	def MedianOfArrays(self, array1, array2):
		return sorted(array1 + array2)[len(array1 + array2) // 2] if len(array1 + array2) & 1 else int((sorted(array1 + array2)[len(array1 + array2) // 2 - 1] + sorted(array1 + array2)[len(array1 + array2) // 2]) / 2) if (sorted(array1 + array2)[len(array1 + array2) // 2 - 1] + sorted(array1 + array2)[len(array1 + array2) // 2]) / 2 % 1 == 0 else (sorted(array1 + array2)[len(array1 + array2) // 2 - 1] + sorted(array1 + array2)[len(array1 + array2) // 2]) / 2


import sys

class Solution:

	def MedianOfArrays(self, a, b):
		s = len(a) + len(b)
		h = s // 2
		if len(a) > len(b):
			(a, b) = (b, a)
		l = 0
		r = len(a)
		while l <= r:
			mid1 = (l + r) // 2
			mid2 = h - mid1
			l1 = a[mid1 - 1] if mid1 - 1 >= 0 else -sys.maxsize
			l2 = b[mid2 - 1] if mid2 - 1 >= 0 else -sys.maxsize
			r1 = a[mid1] if mid1 < len(a) else sys.maxsize
			r2 = b[mid2] if mid2 < len(b) else sys.maxsize
			if l1 <= r2 and l2 <= r1:
				if s % 2 == 0:
					if (max(l1, l2) + min(r1, r2)) % 2 == 0:
						return (max(l1, l2) + min(r1, r2)) // 2
					return (max(l1, l2) + min(r1, r2)) / 2
				return min(r1, r2)
			if l1 > r2:
				r = mid1 - 1
			else:
				l = mid1 + 1
		return -1


class Solution:

	def MedianOfArrays(self, array1, array2):
		b = array1 + array2
		c = sorted(b)
		k = len(c)
		if k % 2 == 0:
			return str((c[k // 2] + c[k // 2 - 1]) / 2).rstrip('.0')
			pass
		else:
			return c[k // 2]


class Solution:

	def MedianOfArrays(self, array1, array2):
		for i in array2:
			array1.append(i)
		array1.sort()
		if len(array1) % 2 != 0:
			return array1[len(array1) // 2]
		elif (array1[len(array1) // 2] + array1[len(array1) // 2 - 1]) % 2 == 0:
			return int((array1[len(array1) // 2] + array1[len(array1) // 2 - 1]) / 2)
		else:
			return float((array1[len(array1) // 2] + array1[len(array1) // 2 - 1]) / 2)


class Solution:

	def MedianOfArrays(self, array1, array2):
		array1.extend(array2)
		array1.sort()
		x = len(array1)
		y = x // 2
		if x % 2 == 0:
			z = array1[y - 1] + array1[y]
			if z % 2 == 0:
				k = z // 2
			else:
				k = z / 2
			return k
		else:
			k = array1[y]
			return k


class Solution:

	def MedianOfArrays(self, array1, array2):
		for i in array2:
			array1.append(i)
		array1 = sorted(array1)
		n = len(array1)
		if n % 2 != 0:
			return array1[n // 2]
		else:
			a = array1[n // 2 - 1]
			b = array1[n // 2]
			c = (a + b) / 2
			if c == int(c):
				return int(c)
			else:
				return c


class Solution:

	def MedianOfArrays(self, array1, array2):
		array1.extend(array2)
		array1.sort()
		if len(array1) % 2 != 0:
			return array1[len(array1) // 2]
		elif (array1[len(array1) // 2] + array1[len(array1) // 2 - 1]) % 2 != 0:
			return (array1[len(array1) // 2] + array1[len(array1) // 2 - 1]) / 2
		else:
			return (array1[len(array1) // 2] + array1[len(array1) // 2 - 1]) // 2


class Solution:

	def MedianOfArrays(self, array1, array2):
		arr = []
		n = len(array1)
		m = len(array2)
		(i, j) = (0, 0)
		while i != n and j != m:
			if array1[i] > array2[j]:
				arr.append(array2[j])
				j += 1
			else:
				arr.append(array1[i])
				i += 1
		if i == n:
			while j != m:
				arr.append(array2[j])
				j += 1
		else:
			while i != n:
				arr.append(array1[i])
				i += 1
		l = len(arr)
		if l % 2 == 0:
			a = arr[(l - 1) // 2]
			b = arr[(l - 1) // 2 + 1]
			if (a + b) / 2 == (a + b) // 2:
				return (a + b) // 2
			else:
				return (a + b) / 2
		else:
			return arr[l // 2]


import math

class Solution:

	def MedianOfArrays(self, a1, a2):
		n = len(a1)
		m = len(a2)
		if n == 0 and m == 1:
			return a2[0]
		elif m == 0 and n == 1:
			return a1[0]
		if n > m:
			end = m
			other = n
			a = a2
			b = a1
		else:
			end = n
			other = m
			a = a1
			b = a2
		beg = 0
		middle = math.ceil((n + m) / 2)
		odd = False if (n + m) % 2 == 0 else True
		while beg <= end:
			cut1 = int((beg + end) / 2)
			cut2 = middle - cut1
			l1 = -float('inf') if cut1 == 0 else a[cut1 - 1]
			l2 = -float('inf') if cut2 == 0 else b[cut2 - 1]
			r1 = float('inf') if cut1 == len(a) else a[cut1]
			r2 = float('inf') if cut2 == len(b) else b[cut2]
			if l1 <= r2 and l2 <= r1:
				if odd:
					return max(l1, l2)
				else:
					ans = max(l1, l2) + min(r1, r2)
					if ans % 2 == 0:
						return ans >> 1
					else:
						return ans / 2.0
			if l1 > r2:
				end = cut1 - 1
			if l2 > r1:
				beg = cut1 + 1
		return 1


class Solution:

	def MedianOfArrays(self, arr1, arr2):
		arr = arr1 + arr2
		arr.sort()
		if len(arr) % 2 != 0:
			return arr[len(arr) // 2]
		else:
			res = (arr[len(arr) // 2] + arr[len(arr) // 2 - 1]) / 2
			if int(res) == res:
				return int(res)
			return res


class Solution:

	def MedianOfArrays(self, array1, array2):
		arr = []
		i = 0
		j = 0
		while i < len(array1) and j < len(array2):
			if array1[i] <= array2[j]:
				arr.append(array1[i])
				i = i + 1
			else:
				arr.append(array2[j])
				j = j + 1
		while i < len(array1):
			arr.append(array1[i])
			i = i + 1
		while j < len(array2):
			arr.append(array2[j])
			j = j + 1
		if len(arr) % 2 != 0:
			return arr[len(arr) // 2]
		else:
			m = len(arr) // 2
			if (arr[m] + arr[m - 1]) % 2 == 0:
				return (arr[m] + arr[m - 1]) // 2
			else:
				return (arr[m] + arr[m - 1]) / 2


import statistics

class Solution:

	def MedianOfArrays(self, array1, array2):
		array1.extend(array2)
		array1.sort()
		l = list(array1)
		res = statistics.median(l)
		if int(res) == res:
			return int(res)
		return res


class Solution:

	def MedianOfArrays(self, arr1, arr2):
		(n1, n2) = (len(arr1), len(arr2))
		if n2 < n1:
			return self.MedianOfArrays(arr2, arr1)
		(low, high) = (0, n1)
		while low <= high:
			cut1 = (low + high) // 2
			cut2 = (n1 + n2 + 1) // 2 - cut1
			if cut1 == 0:
				l1 = float('-inf')
			else:
				l1 = arr1[cut1 - 1]
			if cut2 == 0:
				l2 = float('-inf')
			else:
				l2 = arr2[cut2 - 1]
			if cut1 == n1:
				r1 = float('inf')
			else:
				r1 = arr1[cut1]
			if cut2 == n2:
				r2 = float('inf')
			else:
				r2 = arr2[cut2]
			if l1 <= r2 and l2 <= r1:
				if (n1 + n2) % 2 == 0:
					sumi = max(l1, l2) + min(r1, r2)
					if sumi % 2 == 0:
						return sumi // 2
					return sumi / 2
				else:
					return max(l1, l2)
			elif l1 > r2:
				high = cut1 - 1
			else:
				low = cut1 + 1
		return 0


class Solution:

	def MedianOfArrays(self, a1, a2):
		a = sorted(a1 + a2)
		n = len(a)
		if n % 2 == 0:
			return str((a[n // 2] + a[n // 2 - 1]) / 2).rstrip('.0')
		else:
			return a[n // 2]


class Solution:

	def MedianOfArrays(self, array1, array2):
		if len(array1) > len(array2):
			return self.MedianOfArrays(array2, array1)
		n1 = len(array1)
		n2 = len(array2)
		midinmerged = (n1 + n2 + 1) // 2
		low = 0
		high = n1
		while low <= high:
			mid = (low + high) // 2
			lcut1 = mid
			lcut2 = midinmerged - mid
			if lcut1 == 0:
				l1 = -99989
			else:
				l1 = array1[lcut1 - 1]
			if lcut2 == 0:
				l2 = -99989
			else:
				l2 = array2[lcut2 - 1]
			if lcut1 == n1:
				r1 = 99989
			else:
				r1 = array1[lcut1]
			if lcut2 == n2:
				r2 = 99989
			else:
				r2 = array2[lcut2]
			if l1 <= r2 and l2 <= r1:
				if (n1 + n2) % 2 == 0:
					median = (max(l1, l2) + min(r1, r2)) / 2
					if median % 1 == 0:
						return int(median)
					else:
						return median
				else:
					return max(l1, l2)
			elif l1 > r2:
				high = mid - 1
			else:
				low = mid + 1
		return -1


class Solution:

	def MedianOfArrays(self, array1, array2):
		arr = [0] * (len(array1) + len(array2))
		(i, j, k) = (0, 0, 0)
		while i < len(array1) and j < len(array2):
			if array1[i] <= array2[j]:
				arr[k] = array1[i]
				i += 1
				k += 1
			else:
				arr[k] = array2[j]
				j += 1
				k += 1
		while i < len(array1):
			arr[k] = array1[i]
			k += 1
			i += 1
		while j < len(array2):
			arr[k] = array2[j]
			k += 1
			j += 1
		n = len(array1) + len(array2)
		if n % 2 == 0:
			k = (arr[n // 2 - 1] + arr[n // 2]) / 2
			return int(k) if int(k) == k else k
		else:
			return arr[n // 2]


class Solution:

	def MedianOfArrays(self, array1, array2):
		i = 0
		j = 0
		arr = []
		while i < len(array1) and j < len(array2):
			if array1[i] < array2[j]:
				arr.append(array1[i])
				i += 1
			else:
				arr.append(array2[j])
				j += 1
		while i < len(array1):
			arr.append(array1[i])
			i += 1
		while j < len(array2):
			arr.append(array2[j])
			j += 1
		if len(arr) % 2 == 0:
			a = (arr[len(arr) // 2] + arr[len(arr) // 2 - 1]) / 2
			if a % 1 != 0:
				pass
			else:
				a = int(a)
		else:
			a = arr[len(arr) // 2]
		return a


class Solution:

	def MedianOfArrays(self, array1, array2):
		i = 0
		j = 0
		k = 0
		m = (len(array1) + len(array2)) // 2
		na = []
		if array1 == False:
			return median(array2)
		if array2 == False:
			return median(array1)
		while k <= m:
			if i == len(array1):
				na.append(array2[j])
				j += 1
			elif j == len(array2):
				na.append(array1[i])
				i += 1
			elif array1[i] < array2[j]:
				na.append(array1[i])
				i += 1
			else:
				na.append(array2[j])
				j += 1
			k += 1
		if (len(array1) + len(array2)) % 2 == 1:
			return na[-1]
		elif (na[-1] + na[-2]) % 2 == 0:
			return (na[-1] + na[-2]) // 2
		else:
			return (na[-1] + na[-2]) / 2