[Java/Python 3] Sort and Binary search w/ brief explanation and analysis.
Q & A\n\nQ1: Why and how do we need to compute the factor?\nA1: \n1) We need a factor from potions to multiply with current spells[i] in order to get a product 
**Q & A**\n\nQ1: Why and how do we need to compute the factor?\nA1: \n1) We need a factor from `potions` to multiply with current `spells[i]` in order to get a product at least `success`. Therefore, computing before hand will obtain a key (the factor) for binary search.\n2) `(success + s) // s = success / s + 1`, which is not ceiling of `success / s`; In contrast, `success / s <= (success + s - 1) // s < success / s + 1`, and therefore `(success + s - 1) // s` is the ceiling. \n\nQ2: Why in Python 3 code do we need to compute the ceiling `(success + s - 1) // s`, not `success / s`?\nA2: For this problem we can use either. ~~~However, if `potions` is a float array then the ceiling way is a must. `success / s` is a float, which has a limited precision. In extreme case it may cause error; Use the ceiling, an int, will guarantee the correctness of the code.~~~\n\n~~~e.g., `success = 10, s = 3`, `potions[i] = 3.3333333333...33` (there are `k + 1` 3\'s) is in `potions`.~~~\n\n~~~If we use float `factor = success / s = 10 / 3 = 3.3333333333...3` (there are `k` 3\'s), then we will miss the correct `potions[i]` in binary search;~~~\n~~~In contrast, `(success + s - 1) // s = (10 + 3 - 1) // 3 = 4` will guarantee to obtain correct result.~~~\n\n**End of Q & A**\n\n----\n\n1. Sort `potions` for binary search;\n2. Traverse `spells`, for each element `s`, compute the ceiling of the quotient of `success / s`, `(success + s - 1) / s`;\n3. Binary search the corresponding ceiling of each quotient in 2. to find out how many pairs with a product at least `success`.\n\n```java\n    public int[] successfulPairs(int[] spells, int[] potions, long success) {\n        Arrays.sort(potions);\n        int[] pairs = new int[spells.length];\n        for (int i = 0; i < spells.length; ++i) {\n            if ((success + spells[i] - 1) / spells[i] > 100_000) { // boundary check to avoid int overflow.\n                int s = spells[i], factor = (int)((success + s - 1) / s);\n                pairs[i] = potions.length - binarySearch(potions, factor);\n            } \n        }\n        return pairs;\n    }\n    private int binarySearch(int[] potions, int key) {\n        int lo = 0, hi = potions.length; \n        while (lo < hi) {\n            int mid = lo + (hi - lo) / 2;\n            if (potions[mid] < key) {\n                lo = mid + 1;\n            }else {\n                hi = mid;\n            } \n        }\n        return lo;\n    }\n```\nWe can modify signature of `binarySearch(int[], int)` to `binarySearch(int[], long)` to avoid int overflow problem.\n```java\n    public int[] successfulPairs(int[] spells, int[] potions, long success) {\n        Arrays.sort(potions);\n        int[] pairs = new int[spells.length];\n        for (int i = 0; i < spells.length; ++i) {\n            long factor = (success + spells[i] - 1) / spells[i];\n            pairs[i] = potions.length - binarySearch(potions, factor);\n        }\n        return pairs;\n    }\n    private int binarySearch(int[] potions, long key) {\n        int lo = 0, hi = potions.length; \n        while (lo < hi) {\n            int mid = lo + (hi - lo) / 2;\n            if (potions[mid] < key) {\n                lo = mid + 1;\n            }else {\n                hi = mid;\n            } \n        }\n        return lo;\n    }\n```\n\n```python\n    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n        potions.sort()\n        pairs = []\n        for s in spells:\n            factor = (success + s - 1) // s\n            pairs.append(len(potions) - bisect.bisect_left(potions, factor))\n        return pairs\n```\n\nFor Python 3 code, we can use `success / s` as key for binary search:\n\n```python\n    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n        potions.sort()\n        return [len(potions) - bisect.bisect_left(potions, success / s) for s in spells]\n```\n\n**Analysis:**\n\nTime: `O((m + n)logm)`, space: `O(n + m)` - including sorting space, where `n = spells.length, m = potions.length`.
['Binary Search', 'Sorting', 'Java', 'Python3']