using System;

using System.Collections;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        //int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19};

        //int[] b = {0, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 153, 156, 159, 162, 165, 168, 171, 174, 177, 180, 183, 186, 189, 192, 195, 198, 201, 204, 207, 210, 213, 216, 219, 222, 225, 228, 231, 234, 237, 240, 243, 246, 249, 252, 255, 258, 261, 264, 267, 270, 273, 276, 279, 282, 285, 288, 291, 294, 297};

        //int[] a = {-10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188};

        //int[] b = {300, 302, 304, 306, 308, 310, 312, 314, 316, 318, 320, 322, 324, 326, 328, 330, 332, 334, 336, 338};

        int[] a = { 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95};

        int[] b = {40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58 };

        List<int> abList = new List<int>();

        foreach (int element in a) {abList.Add(element);}

        foreach (int element in b) {abList.Add(element);}

        abList.Sort();

        int[] ab = abList.ToArray();

        double abSolved = MedianOfArray(ab);

        Console.WriteLine("Median:\t" + FindMedianSortedArrays(a, b));

        Console.WriteLine("Should be:\t" + abSolved);

    }

    public static double FindMedianSortedArrays(int[] nums1, int[] nums2) 

    {

        int[] lower;

        int lowerMed;

        int[] greater;

        int greaterMed;

        int AboveMedian = 0; 

        int BelowMedian = 0;

        int totalEliminated = 0;

        int totalElements = nums1.Length + nums2.Length;

        // 1st round arbitrary

        if (nums1[nums1.Length / 2] <= nums2[nums2.Length / 2])

        {

            lower = nums1;

            lowerMed = lower.Length / 2;

            greater = nums2;

            greaterMed = greater.Length / 2;

        }

        else

        {

            lower = nums2;

            lowerMed = lower.Length / 2;

            greater = nums1;

            greaterMed = greater.Length / 2;

        }

        if (lower.Length == greater.Length)

            ;

        else if (lower.Length % 2 == 0)

            lowerMed--;

        // not 100% why ONLY when low isnt even

        // and high is then high needs increment down

        else if (greater.Length % 2 == 0 && greater.Length > lower.Length)

            greaterMed--;

        //debug                                                                                     //

        Console.Write("Initial lower: { ");                                                         //

        foreach (int element in lower) { Console.Write($"{element} ");}                             //

        Console.Write($"}} n = {lower.Length}\n");                                                  //

        Console.WriteLine($"lower median is lower[{lowerMed}] = {lower[lowerMed]}");                //

        Console.Write("\n");                                                                        //

        Console.Write("Initial greater: { ");                                                       //

        foreach (int element in greater) { Console.Write($"{element} ");}                           //

        Console.Write($"}} n = {greater.Length}\n");                                                //

        Console.WriteLine($"greater median is greater[{greaterMed}] = {greater[greaterMed]}");      //

        Console.Write("\n");                                                                        //

        //exception

        if (lower[lowerMed] == greater[greaterMed])

            if (lower.Length % 2 == 0 && greater.Length % 2 == 0 )

                return MedianOfInts(lower[lowerMed],Math.Max(lower[lowerMed - 1],greater[greaterMed - 1]));

            else

                return lower[lowerMed];

        while (lower.Length > 1 && greater.Length > 1)

        {

        lower = lower[(lowerMed + 1)..];

        greater = greater[..(greaterMed)];

        //debug                                                                                     //

        Console.Write("new lower: { ");                                                             //

        foreach (int element in lower) { Console.Write($"{element} ");}                             //

        Console.Write($"}} n = {lower.Length}\n");                                                  //

        Console.Write("new greater: { ");                                                           //

        foreach (int element in greater) { Console.Write($"{element} ");}                           //

        Console.Write($"}} n = {greater.Length}\n");                                                //

        //end debug

        var shift = calculateShift(lower, greater);

        lowerMed = shift - 1;

​

        greaterMed = greater.Length - shift;

        //debug

        Console.WriteLine($"\nlower median is lower[{lowerMed}] = {lower[lowerMed]}");              //

        Console.Write("\n");                                                                        //

        Console.WriteLine($"\ngreater median is greater[{greaterMed}] = {greater[greaterMed]}");    //

        Console.Write("\n");                                                                        //

​

​

        //debug                                                                                     //

        AboveMedian += shift;                                                                       //

        BelowMedian += shift;                                                                       //

        totalEliminated += shift * 2;                                                               //

                                                                                                    //

        Console.WriteLine($"{BelowMedian} bottom values have been eliminated from lower[]");        //

        Console.WriteLine($"{AboveMedian} upper values have been eliminated from greater[]");       //

        Console.WriteLine($"{totalEliminated} / {totalElements}");                                  //

        //end debug

        if (lower[lowerMed] > greater[greaterMed])

        {

            Console.WriteLine("\nThe arrays swapped places\n");

            //temp for swap

            int[] temp = lower;

            lower = greater;

            lowerMed = lower.Length / 2;

            greater = temp;

            greaterMed = greater.Length / 2;

        }

        } // end while loop

        if (lower.Length == 1)

        {

            if ((nums1.Length + nums2.Length) % 2 == 0)

            {

                if (lower[lowerMed] < greater[greaterMed - 1])

                {

                    return MedianOfInts(greater[greaterMed], greater[greaterMed - 1]);

                }

                else

                    return MedianOfInts(greater[greaterMed], lower[0]);

            }

            else

                return greater[greaterMed];

        }

        else

        {

            if ((nums1.Length + nums2.Length) % 2 == 0)

            {

                if (lower[lowerMed + 1] < greater[greaterMed])

                {

                    return MedianOfInts(lower[lowerMed], lower[lowerMed + 1]);

                }

                else

                    return MedianOfInts(lower[lowerMed], greater[0]);

            }

            else

                return lower[lowerMed];

        }

        return -1;

    }

    public static double MedianOfArray(int[] a)

    {

        if (a.Length % 2 == 0)

            return (a[(a.Length - 1) / 2] + a[a.Length / 2]) / 2.0;

        else

            return (a[a.Length / 2]);

    }

    public static double MedianOfInts(int a, int b)

    {

        return (a+b)/2.0;

    }

    public static int calculateShift(int[] low, int[] high)

    {

        // lower shift is from [-1] to new median

        int lowerShift = (low.Length / 2) + 1;

        // for the larger array the shift goes from the old median (now high.Length)

        // to the new median of the low range (high.Length / 2)

        int greaterShift = high.Length - (high.Length / 2);

        // cut this out later - debug

        if (lowerShift > greaterShift)

            Console.WriteLine($"greaterShift is a smaller jump, shift = {greaterShift}");

        else if (lowerShift < greaterShift)

            Console.WriteLine($"lowerShift is a smaller jump, shift = {lowerShift}");

        else

            Console.WriteLine($"shifts are equal, shift = {lowerShift}");

        return Math.Min(lowerShift, greaterShift);

    }

}