Repository: TheAlgorithms/Java
Pull request #5554 (2024-10-03 14:40:22)

Add `MedianOfTwoSortedArrays.java` new algorithm
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5554?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `77.27273%` with `5 lines` in your changes missing coverage. Please review.
> Project coverage is 52.99%. Comparing base [(`842ff52`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/842ff5294f5e97dfd1e4c09f9d9e01a89ac16e32?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`ac398d3`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/ac398d345ea7b979d75bbe107ad59f4d34f3ea5f?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).
> Report is 8 commits behind head on master.

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5554?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...thms/divideandconquer/MedianOfTwoSortedArrays.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5554?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdivideandconquer%2FMedianOfTwoSortedArrays.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kaXZpZGVhbmRjb25xdWVyL01lZGlhbk9mVHdvU29ydGVkQXJyYXlzLmphdmE=) | 77.27% | [2 Missing and 3 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5554?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5554      +/-   ##
============================================
+ Coverage     52.31%   52.99%   +0.68%     
- Complexity     3259     3318      +59     
============================================
  Files           526      530       +4     
  Lines         15205    15365     +160     
  Branches       2892     2933      +41     
============================================
+ Hits           7954     8143     +189     
+ Misses         6924     6884      -40     
- Partials        327      338      +11     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5554?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

alxkm: It looks like it's [leetcode](https://leetcode.com/problems/median-of-two-sorted-arrays/description/), so according to the rules of this repository it can't be added.

https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md

What do you think @siriak 
Hardvan: I understand the concern about it being a LeetCode problem. However, I believe this implementation touches on a valid algorithm that has practical applications. Given its relevance and utility in algorithm studies, I think it warrants consideration for inclusion in the repository.
siriak: @Hardvan could you provide some links that explain this algorithm and its applications outside of leetcode context? If no, we cannot include it as it's too specific and only appears in the context of coding competitions.
Hardvan: @siriak The [Algorithms/Python repository](https://github.com/TheAlgorithms/Python/blob/master/data_structures/arrays/median_two_array.py) includes the "Median of Two Sorted Arrays" algorithm as part of its directory, indicating it is recognized as a valid algorithm beyond coding competitions.
Hardvan: Conflicts resolved!
Hardvan: I have refactored the test code to use Parameterized tests instead,

Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index 6042dd1b..af1e4f28 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -31,6 +31,7 @@
             * [IsPowerTwo](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/IsPowerTwo.java)
             * [LowestSetBit](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/LowestSetBit.java)
             * [NonRepeatingNumberFinder](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/NonRepeatingNumberFinder.java)
+            * [NumberAppearingOddTimes](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/NumberAppearingOddTimes.java)
             * [NumbersDifferentSigns](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/NumbersDifferentSigns.java)
             * [ReverseBits](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/ReverseBits.java)
             * [SingleBitOperations](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/bitmanipulation/SingleBitOperations.java)
@@ -228,6 +229,7 @@
           * divideandconquer
             * [BinaryExponentiation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/BinaryExponentiation.java)
             * [ClosestPair](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/ClosestPair.java)
+            * [MedianOfTwoSortedArrays](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArrays.java)
             * [SkylineAlgorithm](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/SkylineAlgorithm.java)
             * [StrassenMatrixMultiplication](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/divideandconquer/StrassenMatrixMultiplication.java)
           * dynamicprogramming
@@ -638,6 +640,7 @@
             * [IsPowerTwoTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/IsPowerTwoTest.java)
             * [LowestSetBitTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/LowestSetBitTest.java)
             * [NonRepeatingNumberFinderTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/NonRepeatingNumberFinderTest.java)
+            * [NumberAppearingOddTimesTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/NumberAppearingOddTimesTest.java)
             * [NumbersDifferentSignsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/NumbersDifferentSignsTest.java)
             * [ReverseBitsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/ReverseBitsTest.java)
             * [SingleBitOperationsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/bitmanipulation/SingleBitOperationsTest.java)
@@ -729,6 +732,7 @@
               * [LeftistHeapTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/heaps/LeftistHeapTest.java)
             * lists
               * [CircleLinkedListTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/CircleLinkedListTest.java)
+              * [CreateAndDetectLoopTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/CreateAndDetectLoopTest.java)
               * [QuickSortLinkedListTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/QuickSortLinkedListTest.java)
               * [ReverseKGroupTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/ReverseKGroupTest.java)
               * [RotateSinglyLinkedListsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/lists/RotateSinglyLinkedListsTest.java)
@@ -773,6 +777,7 @@
           * divideandconquer
             * [BinaryExponentiationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/BinaryExponentiationTest.java)
             * [ClosestPairTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/ClosestPairTest.java)
+            * [MedianOfTwoSortedArraysTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArraysTest.java)
             * [SkylineAlgorithmTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/SkylineAlgorithmTest.java)
             * [StrassenMatrixMultiplicationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/divideandconquer/StrassenMatrixMultiplicationTest.java)
           * dynamicprogramming
diff --git a/src/main/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArrays.java b/src/main/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArrays.java
new file mode 100644
index 00000000..d9e51442
--- /dev/null
+++ b/src/main/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArrays.java
@@ -0,0 +1,53 @@
+package com.thealgorithms.divideandconquer;
+
+public final class MedianOfTwoSortedArrays {
+
+    private MedianOfTwoSortedArrays() {
+    }
+
+    /**
+     * Finds the median of two sorted arrays in logarithmic time.
+     *
+     * @param nums1 the first sorted array
+     * @param nums2 the second sorted array
+     * @return the median of the combined sorted array
+     * @throws IllegalArgumentException if the input arrays are not sorted
+     */
+    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
+        if (nums1.length > nums2.length) {
+            return findMedianSortedArrays(nums2, nums1); // Ensure nums1 is the smaller array
+        }
+
+        int m = nums1.length;
+        int n = nums2.length;
+        int low = 0;
+        int high = m;
+        while (low <= high) {
+            int partition1 = (low + high) / 2; // Partition in the first array
+            int partition2 = (m + n + 1) / 2 - partition1; // Partition in the second array
+
+            int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
+            int minRight1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];
+            int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
+            int minRight2 = (partition2 == n) ? Integer.MAX_VALUE : nums2[partition2];
+
+            // Check if partition is valid
+            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
+                // If combined array length is odd
+                if (((m + n) & 1) == 1) {
+                    return Math.max(maxLeft1, maxLeft2);
+                }
+                // If combined array length is even
+                else {
+                    return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
+                }
+            } else if (maxLeft1 > minRight2) {
+                high = partition1 - 1;
+            } else {
+                low = partition1 + 1;
+            }
+        }
+
+        throw new IllegalArgumentException("Input arrays are not sorted");
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArraysTest.java b/src/test/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArraysTest.java
new file mode 100644
index 00000000..6cfbc237
--- /dev/null
+++ b/src/test/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArraysTest.java
@@ -0,0 +1,41 @@
+package com.thealgorithms.divideandconquer;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+public class MedianOfTwoSortedArraysTest {
+
+    @ParameterizedTest
+    @MethodSource("provideTestCases")
+    void testFindMedianSortedArrays(int[] nums1, int[] nums2, double expectedMedian) {
+        assertEquals(expectedMedian, MedianOfTwoSortedArrays.findMedianSortedArrays(nums1, nums2));
+    }
+
+    private static Stream<Arguments> provideTestCases() {
+        return Stream.of(
+            // Test case 1: Arrays of equal length
+            Arguments.of(new int[] {1, 3}, new int[] {2, 4}, 2.5),
+
+            // Test case 2: Arrays of different lengths
+            Arguments.of(new int[] {1, 3}, new int[] {2}, 2.0),
+
+            // Test case 3: Arrays with even total length
+            Arguments.of(new int[] {1, 2, 8}, new int[] {3, 4, 5, 6, 7}, 4.5),
+
+            // Test case 4: Arrays with odd total length
+            Arguments.of(new int[] {1, 2, 8}, new int[] {3, 4, 5}, 3.5),
+
+            // Test case 5: Single element arrays
+            Arguments.of(new int[] {1}, new int[] {3}, 2.0),
+
+            // Test case 6: Empty arrays
+            Arguments.of(new int[] {}, new int[] {0}, 0.0),
+
+            // Test case 7: Same element arrays
+            Arguments.of(new int[] {2, 2, 2}, new int[] {2, 2, 2}, 2.0));
+    }
+}