Example: Median of Two Sorted Arrays (Binary Search Approach)

// Median of Two Sorted Arrays (Binary Search Approach)
#include <stdio.h>
#include <limits.h> // 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;
}