Previous Next

Find Median of Two Sorted Arrays

TCS NQT Coding Hard Go Ad-Free - ₹20/mo

Given two sorted arrays nums1 and nums2, return the median of the two sorted arrays. The solution must use binary search to achieve an overall run time complexity of O(log(min(m,n))), where m and n are the lengths of nums1 and nums2 respectively.

Examples:

Input: nums1 = [1,3], nums2 = [2]

Output: 2.0

Explanation: The merged array is [1,2,3] and the median is 2.

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.5

Explanation: The merged array is [1,2,3,4] and the median is (2+3)/2 = 2.5.

Input: nums1 = [0,0], nums2 = [0,0]

Output: 0.0

Explanation: The merged array consists of all zeros, so the median is 0.0.

Constraints

  • Arrays nums1 and nums2 are sorted in non-decreasing order.
  • 0 ≤ nums1.length, nums2.length ≤ 10^5
  • -10^6 ≤ nums1[i], nums2[i] ≤ 10^6
  • The median is the middle value if the total number of elements is odd, or the average of the two middle values if even.
  • The algorithm must use binary search and run in O(log(min(m,n))) time.