C Online Compiler
Example: Median of Two Sorted Arrays (Binary Search Approach)
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// Median of Two Sorted Arrays (Binary Search Approach) #include
#include
// For INT_MIN, INT_MAX // Helper function to find the maximum of two integers int max(int a, int b) { return (a > b) ? a : b; } // Helper function to find the minimum of two integers int min(int a, int b) { return (a < b) ? a : b; } double findMedianSortedArrays_BinarySearch(int* nums1, int nums1Size, int* nums2, int nums2Size) { // Step 1: Ensure nums1 is the shorter array for binary search optimization if (nums1Size > nums2Size) { return findMedianSortedArrays_BinarySearch(nums2, nums2Size, nums1, nums1Size); } int low = 0; int high = nums1Size; // Binary search range for partition in nums1 int totalLen = nums1Size + nums2Size; int halfLen = (totalLen + 1) / 2; // Number of elements in the left half while (low <= high) { int partitionX = low + (high - low) / 2; // Partition point in nums1 int partitionY = halfLen - partitionX; // Partition point in nums2 // Determine left_max and right_min for both partitions // If partition is at 0, left_max is INT_MIN // If partition is at array size, right_min is INT_MAX int maxX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1]; int minX = (partitionX == nums1Size) ? INT_MAX : nums1[partitionX]; int maxY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1]; int minY = (partitionY == nums2Size) ? INT_MAX : nums2[partitionY]; // Check if we found the correct partition if (maxX <= minY && maxY <= minX) { // Correct partition found // Median calculation depends on total length (even/odd) if (totalLen % 2 == 1) { // Odd total length return (double)max(maxX, maxY); } else { // Even total length return (double)(max(maxX, maxY) + min(minX, minY)) / 2.0; } } else if (maxX > minY) { // PartitionX is too far to the right, need to move left in nums1 high = partitionX - 1; } else { // maxY > minX // PartitionX is too far to the left, need to move right in nums1 low = partitionX + 1; } } // Should not reach here if inputs are valid sorted arrays return 0.0; } int main() { // Example 1: Odd total number of elements int nums1_ex1[] = {1, 3}; int nums2_ex1[] = {2}; int nums1Size_ex1 = sizeof(nums1_ex1) / sizeof(nums1_ex1[0]); int nums2Size_ex1 = sizeof(nums2_ex1) / sizeof(nums2_ex1[0]); double median_ex1 = findMedianSortedArrays_BinarySearch(nums1_ex1, nums1Size_ex1, nums2_ex1, nums2Size_ex1); printf("Example 1: nums1 = {1, 3}, nums2 = {2} -> Median: %.1f\n", median_ex1); // Expected: 2.0 // Example 2: Even total number of elements int nums1_ex2[] = {1, 2}; int nums2_ex2[] = {3, 4}; int nums1Size_ex2 = sizeof(nums1_ex2) / sizeof(nums1_ex2[0]); int nums2Size_ex2 = sizeof(nums2_ex2) / sizeof(nums2_ex2[0]); double median_ex2 = findMedianSortedArrays_BinarySearch(nums1_ex2, nums1Size_ex2, nums2_ex2, nums2Size_ex2); printf("Example 2: nums1 = {1, 2}, nums2 = {3, 4} -> Median: %.1f\n", median_ex2); // Expected: 2.5 // Example 3: Different lengths int nums1_ex3[] = {0, 0}; int nums2_ex3[] = {0, 0}; int nums1Size_ex3 = sizeof(nums1_ex3) / sizeof(nums1_ex3[0]); int nums2Size_ex3 = sizeof(nums2_ex3) / sizeof(nums2_ex3[0]); double median_ex3 = findMedianSortedArrays_BinarySearch(nums1_ex3, nums1Size_ex3, nums2_ex3, nums2Size_ex3); printf("Example 3: nums1 = {0, 0}, nums2 = {0, 0} -> Median: %.1f\n", median_ex3); // Expected: 0.0 // Example 4: One empty array int nums1_ex4[] = {}; int nums2_ex4[] = {2, 3}; int nums1Size_ex4 = sizeof(nums1_ex4) / sizeof(nums1_ex4[0]); int nums2Size_ex4 = sizeof(nums2_ex4) / sizeof(nums2_ex4[0]); double median_ex4 = findMedianSortedArrays_BinarySearch(nums1_ex4, nums1Size_ex4, nums2_ex4, nums2Size_ex4); printf("Example 4: nums1 = {}, nums2 = {2, 3} -> Median: %.1f\n", median_ex4); // Expected: 2.5 // Example 5: Larger case int nums1_ex5[] = {1, 5, 9}; int nums2_ex5[] = {2, 4, 6}; int nums1Size_ex5 = sizeof(nums1_ex5) / sizeof(nums1_ex5[0]); int nums2Size_ex5 = sizeof(nums2_ex5) / sizeof(nums2_ex5[0]); double median_ex5 = findMedianSortedArrays_BinarySearch(nums1_ex5, nums1Size_ex5, nums2_ex5, nums2Size_ex5); printf("Example 5: nums1 = {1, 5, 9}, nums2 = {2, 4, 6} -> Median: %.1f\n", median_ex5); // Expected: 4.5 return 0; }
Output
Clear
ADVERTISEMENTS