✅Binary Insertion 🔥 || C# || Easy Explanation || Beginner Friendly🔥🔥🔥
Intuition\nThis solution aims to segregate the elements in an array into two arrays such that the median element becomes the dividing point, with elements great
# Intuition\nThis solution aims to segregate the elements in an array into two arrays such that the median element becomes the dividing point, with elements greater than the median placed in one array and elements less than or equal to the median placed in the other. It achieves this by leveraging two key ideas:\n\n- **Maintaining sorted lists**: The code utilizes two separate **SortedList** instances to maintain elements in ascending order for each half (one exceeding the median and the other less than or equal to the median).\n- **Counting greater elements**: A custom **GreaterCount** function efficiently determines the number of elements in the corresponding **SortedList** that are greater than the current element.\n\n# Approach\n- Initialization:\n    - Two empty lists - **arr1** and **arr2** - are created to store the final results.\n    - Two **SortedList** instances - **arr1Sort** and **arr2Sort** - are created with a custom **DuplicateKey** to handle duplicate keys.\n    - The first two elements of the input array (**nums**) are added to the respective **lists** and **SortedLists** for initialization.\n- Iterate through remaining elements:\n    - The code iterates through the remaining elements (**i** from 2 to **nums.Length - 1**).\n    - For each element (**nums[i]**), it calls the **GreaterCount** function for both **arr1Sort** and **arr2Sort** to determine the number of elements greater than it in each list.\n    - Based on the comparison of these counts:\n        - If the count in **arr1Sort** (**l**) is greater than the count in **arr2Sort** (**r**), the element is added to **arr1** and **arr1Sort**.\n        - If the count in **arr1Sort** (**l**) is less than the count in **arr2Sort** (**r**), the element is added to **arr2** and **arr2Sort**.\n        - If the counts are equal, the element is added to the list with the fewer elements (**arr1** or **arr2**) and its corresponding **SortedList**.\n- Finally, the elements from both lists (**arr1** and **arr2**) are combined using **Concat** and converted to an array to form the final output.\n\n# Complexity\n- Time complexity: **O(n * log n)**\n    - **GreaterCount function**: This function performs a binary search on a sorted list with a maximum of **log n** comparisons in the worst case.\n    - **Overall loop**: The loop iterates through **n-2** elements of the input array (**nums.Length - 2**). Inside the loop, the **GreaterCount**  function is called twice, contributing **2 * log n** per iteration.\n\n- Space complexity: **O(n)**\n    - Two **SortedList** instances are used, each potentially storing all elements from the input array.\n    - Two additional lists (**arr1** and **arr2**) store elements during processing.\n\n    \n    \n    \n    ![image.png](https://assets.leetcode.com/users/images/48167aa7-3944-4f66-ac52-d4841a446d14_1709743705.998846.png)\n\n\n# Code\n```\npublic partial class Solution {\n    public int[] ResultArray(int[] nums) {\n\n        var arr1 = new List<int>();\n        var arr2 = new List<int>();\n\n        var arr1Sort = new SortedList<int, int>(new DuplicateKey<int>());\n        var arr2Sort = new SortedList<int, int>(new DuplicateKey<int>());\n\n        arr1.Add(nums[0]);\n        arr2.Add(nums[1]);\n\n        arr1Sort.Add(nums[0], nums[0]);\n        arr2Sort.Add(nums[1], nums[1]);\n\n        for (var i = 2; i < nums.Length; i++) {\n\n            var l = GreaterCount(arr1Sort, nums[i]);\n            var r = GreaterCount(arr2Sort, nums[i]);\n\n            if (l > r) {\n\n                arr1.Add(nums[i]);\n                arr1Sort.Add(nums[i], nums[i]);\n            }\n            else if (l < r) {\n\n                arr2.Add(nums[i]);\n                arr2Sort.Add(nums[i], nums[i]);\n            }\n            else {\n\n                var check = arr1.Count > arr2.Count;\n                (check ? arr2 : arr1).Add(nums[i]);\n                (check ? arr2Sort : arr1Sort).Add(nums[i], nums[i]);\n            }\n        }\n        return arr1.Concat(arr2).ToArray();\n    }\n\n    private int GreaterCount(SortedList<int, int> arr, int val) {\n\n        var l = 0;\n        var r = arr.Count - 1;\n        var count = arr.Count;\n\n        while(l <= r) {\n\n            var mid = l + (r - l) / 2;\n            if (arr.Values[mid] > val) {\n\n                r = mid - 1;\n                count = mid;\n            }\n            else l = mid + 1;\n        }\n        return arr.Count - count;\n    }\n}\n\npublic class DuplicateKey<TKey> : IComparer<TKey> where TKey : IComparable {\n\n    public int Compare(TKey x, TKey y) {\n\n        var result = x.CompareTo(y);\n        return result == 0 ? 1 : result;\n    }\n}\n```
['Array', 'Binary Search', 'Sorting', 'Simulation', 'Counting', 'C#']