Clear C# Binary Search beats 95.4%
Intuition\n Describe your first thoughts on how to solve this problem. \nAfter sort potions, this problem becomes to: for each spells[i], find the first index i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAfter sort potions, this problem becomes to: for each spells[i], find the first index in potions that spells[i] * potions[index] >= success. Then the pair that spells[i] can form is potions.Length - index\n\nFind the first index match a condition is a typical binary search question.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(mlogm + nlogm)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(1)\n# Code\n```\npublic class Solution {\n    public int[] SuccessfulPairs(int[] spells, int[] potions, long success) {\n             Array.Sort(potions);\n            int[] retval = new int[spells.Length];\n            for(int i = 0; i < spells.Length; i++)\n            {\n                int l = 0, r = potions.Length - 1;\n                int leftMostIdx = -1;\n                while(l <= r)\n                {\n                    int m = (l + r) / 2;\n                    if (((long)spells[i]) * potions[m] >= success)\n                    {\n                        leftMostIdx = m;\n                        r = m - 1;\n                    }\n                    else l = m + 1;\n                }\n                retval[i] = leftMostIdx == -1 ? 0 : potions.Length - leftMostIdx;\n            }\n\n            return retval;       \n    }\n}\n```
['C#']