Summary

The article presents two binary search-based algorithms for finding the median of two sorted arrays, with a focus on achieving an O(log(m+n)) time complexity.

Abstract

The article "LeetCode 4(Golang): Median of Two Sorted Arrays(Hard): Binary Search" delves into the complexities of the LeetCode problem "Median of Two Sorted Arrays." It explores two distinct binary search algorithms designed to solve this problem efficiently. The first solution involves reducing the problem to finding the Kth number in the combined arrays, using a binary search approach that ensures an O(log(m+n)) time complexity and O(1) space complexity. The second solution performs a binary search on the shorter array to find a partition point, which is particularly efficient when there is a significant size difference between the arrays. This approach also maintains the desired time complexity of O(log(min(m,n))) and a space complexity of O(1). The article emphasizes the recursive nature of the first solution and the customized binary search technique of the second solution, showcasing the versatility of binary search algorithms in solving complex problems.

Opinions

The author believes that both solutions are efficient and showcase the power of binary search algorithms in solving complex problems.
The first solution is praised for its recursive strategy, which gradually reduces the problem size until the base case is reached, despite not being a classic recursive function.
The second solution is considered more efficient when there is a significant size difference between the two arrays, as it performs binary search on the shorter array.
The article suggests that understanding these binary search-like solutions can help appreciate their versatility and how they can be ingeniously adapted to solve a variety of problems.
The author encourages readers to share their insights or ask questions, indicating a collaborative and open-ended approach to algorithmic problem-solving.

LeetCode 4(Golang): Median of Two Sorted Arrays(Hard): Binary Search

Discover two unique algorithmic solutions to the problem “Median of Two Sorted Arrays” on LeetCode, diving deep into the logic underpinning each one, along with providing a thorough code commentary.

Introduction

This article will embark on exploring and unraveling the complexities of a LeetCode problem named Median of Two Sorted Arrays. We’ll investigate two unique solutions, both using a binary search-like algorithm but in different ways.

Problem

The problem asks us to find the median of two sorted arrays — nums1 and nums2 – which may differ in size. The overall run time complexity must be O(log(m+n)).

Example

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Solution 1: Reducing The Problem To Find The Kth Element

Solution 1 simplifies the problem by reducing it to finding the Kth number in two sorted arrays. When the total length of two arrays is an odd, the median is the Kth number, where K is half the total length. When it is even, the median is the average of Kth number and the (K-1)th number.

We use a binary search algorithm to find the Kth number. The function findKth takes the parameters nums1, nums2 and k and returns the Kth number in nums1 and nums2.

The time complexity is O(log(m+n)) where m and n are the sizes of nums1 and nums2 respectively. The space complexity is O(1), as it does not use additional space proportional to the size of the input arrays.

In this solution, we recursively halve the arrays, thereby achieving the desired run time complexity and reducing the problem size gradually until it becomes simpler to solve.

Solution 2: Binary Search On The Shorter Array

In Solution 2, we perform the binary search on the shorter array, ensuring that the binary search’s time complexity is O(log(min(m,n))), making it a more efficient approach when the size difference between the two arrays is significant.

This solution uses binary search to find a partition point where elements on the left side are smaller than the elements on the right side. By doing it on the smaller array, it ensures a lesser number of operations, optimizing the solution.

Analysis

How does Solution 1 in Golang use recursion to find the Kth number in two sorted arrays?

Solution 1 uses a recursive approach to gradually narrow down to the Kth number, but it might not be obvious at first glance as it uses a for loop. I will explain in detail about how this recursion-like process helps to find the Kth number in two sorted arrays.

The overall function findKth(nums1, nums2, k), does not directly call itself, as classic recursive functions usually do. However, the logic within this function does indeed take a recursive strategy to approach the problem, by repetitively applying the same set of rules until it reaches the base condition. In this case, the base conditions are when one array nums1 or nums2 becomes empty or k equals 0, making it possible to directly return an answer.

Inside the for loop, the function makes a decision to remove parts of either nums1 or nums2 or both. This is determined by comparing the m1 + m2 with k, and then further comparing the middle number of nums1 with that of nums2. Depending on the comparison results, it discards half of one array or both, this gives us a log(n) time complexity similar to binary search.

After each loop, the function continues to work with the remaining arrays. This is similar to a recursive function call, the function applies the same procedure on a reduced or simpler input, waiting for it to reach the base case.

So, while it might not look like the typical recursive call at first glance, it adopts recursion’s strategies in narrowing down the problem size and working towards the base case.

Can you explain how Solution 2 in Golang uses binary search to find the median of two sorted arrays?

The binary search algorithm used in Solution 2 is different from the typical binary search. Conventionally, binary search is used to find a specific value in a sorted array, but in this problem, we use binary search to locate an optimal partition point that splits the two input arrays, effectively providing us the median value(s).

The function “findMedianSortedArrays” executes a binary search on the shorter array (nums1 in this case). For each attempt, we calculate i and j, which indicate the partition points in nums1 and nums2 respectively.

The procedure ensures that:

The elements on the left of i in nums1 and j in nums2 are smaller than the elements on the right of i and j, in their respective arrays.
We have an equal number of elements on both sides of the partition when both arrays are joined together.

Every iteration of the binary search loop moves the partition position closer towards this desired state. Specifically, if nums1[i-1] > nums2[j], it means the median is in the left part of nums1, so we move the high-pointer of binary search hi to i - 1. Conversely, if nums2[j-1] > nums1[i], the median is in the right part, so we move the low-pointer lo to i + 1.

Finally, when we get the partition point, we can calculate the median by considering different scenarios based on the total number of elements (even or odd) and the relative sizes of the 4 “border” elements nums1[i-1], nums1[i], nums2[j-1], nums2[j].

The binary search ensures that the time complexity is O(log(min(m, n))), where m and n are the lengths of nums1 and nums2, making it a highly efficient solution. Not to mention, the space complexity is O(1), as all variables used in the algorithm take constant space.

Conclusion

Both solutions demonstrated unique techniques to approach the Median of Two Sorted Arrays problem while ensuring logarithmic time complexity. Understanding these approaches helps us appreciate the versatility of binary search-like solutions and how they can be ingeniously customized to solve a variety of seemingly difficult problems. Got different thoughts? How did you approach this problem? Share your insights or ask Q&A! Stay connected for more fascinating algorithm discussions!