#algo/binary-search Firstly, because this is a $\log n$ algorithm, it needs to be using binary search. Secondly, we look at the properties of median. Let's look at an array $\{x_1, x_2, \cdots, x_n\}$. We need to satisfy two variants: 1. the number points on the left of the median is equal to the number of points on the right side of the median; 2. the number of points on the left of the median are all no greater than the median, and the points on the right of the median are all no less than the median. We can fix the first point as an invariant, and optimise the second (because of the sorted property). ## Problem: Median of Two Sorted Arrays Given two sorted arrays `nums1` and `nums2` of size `m` and `n` respectively, return the median of the two sorted arrays. The overall run time complexity should be $O(\log (m+n))$. ### Example 1: - **Input**: `nums1 = [1,3]`, `nums2 = [2]` - **Output**: `2.00000` - **Explanation**: The merged array is `[1,2,3]` and the median is `2`. ### Example 2: - **Input**: `nums1 = [1,2]`, `nums2 = [3,4]` - **Output**: `2.50000` - **Explanation**: The merged array is `[1,2,3,4]` and the median is $(2 + 3) / 2 = 2.5$. ### Constraints: - `nums1.length == m` - `nums2.length == n` - $0 \leq m \leq 1000$ - $0 \leq n \leq 1000$ - $1 \leq m + n \leq 2000$ - $-10^6 \leq \texttt{nums1}[i], \texttt{nums2}[i] \leq 10^6$ --- ## Solution To solve this problem efficiently with $O(\log(m + n))$ complexity, we can use a binary search approach rather than merging the arrays, which would be $O(m + n)$. Here’s a Python solution: ```python def findMedianSortedArrays(nums1, nums2): # Ensure nums1 is the smaller array if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) total_left = (m + n + 1) // 2 # Binary search on the smaller array left, right = 0, m while left < right: i = (left + right) // 2 j = total_left - i if nums1[i] < nums2[j - 1]: left = i + 1 else: right = i i = left j = total_left - i # Find the maximum of the left partition nums1_left_max = float('-inf') if i == 0 else nums1[i - 1] nums2_left_max = float('-inf') if j == 0 else nums2[j - 1] left_max = max(nums1_left_max, nums2_left_max) # If the total length is odd, return the maximum of the left partition if (m + n) % 2 == 1: return left_max # Find the minimum of the right partition nums1_right_min = float('inf') if i == m else nums1[i] nums2_right_min = float('inf') if j == n else nums2[j] right_min = min(nums1_right_min, nums2_right_min) # If the total length is even, return the average of the two middle values return (left_max + right_min) / 2.0 ``` --- ## Explanation 1. **Ensure `nums1` is the smaller array**: This reduces our search space to the smaller array, making the binary search more efficient. 2. **Partitioning**: - Partition `nums1` and `nums2` so the left half has half of the total elements (or one more if the total is odd). - `i` and `j` are the partition indi - ces for `nums1` and `nums2`, respectively. 3. **Binary Search Logic**: - ==Adjust the search space of `nums1` so that the elements on the left side of both arrays are less than or equal to the elements on the right side.== 4. **Calculate the median**: - If the combined length of the arrays is odd, the median is the maximum of the left partition. - If the combined length is even, the median is the average of the maximum of the left partition and the minimum of the right partition. ### Example Walkthrough - **Input**: `nums1 = [1,3]`, `nums2 = [2]` - Merged array is `[1,2,3]`, and the median is `2.00000`. - **Input**: `nums1 = [1,2]`, `nums2 = [3,4]` - Merged array is `[1,2,3,4]`, and the median is $(2 + 3) / 2 = 2.5$.