🚨 [JavaScript][php] - Beats 100% - Binary Search - faster than other solutions
\n# Approach\nHere is my approach to solving the problem using a binary search:\n\n First, we sort the potions array in ascending order. This ensures that the s
\n# Approach\nHere is my approach to solving the problem using a binary search:\n\n* First, we sort the potions array in ascending order. This ensures that the smallest potions are at the front of the\n  array.\n\n* Then, we iterate over the spells array. For each spell, we perform _a binary search_ on the potions array to find the\n  first potion that is greater than or equal to the _success_ value.\n\n* The number of potions that are greater than or equal to the spell\'s power is the number of successful pairs that can\n  be formed with that spell.\n* We add this number to the pairs result array.\n* We continue this process until we have iterated over all of the spells.\n* Finally, we return the pairs array.\n\n# Complexity\n\nThe **time complexity** of the algorithm is O(n log m), where n is the number of potions, and m is the number of spells.\nThis is because the algorithm sorts the potions array in O(n log n) time and performs a binary search on the potions\narray for each spell, which takes O(n*log m) time. => O( (n+m) * log m) => O(n log m)\n\nThe **space complexity** of the algorithm is O(1), since the algorithm only requires a constant amount of space to store\nthe\npotions array, the spells array, the success value, and the pairs array.\n\n```javascript []\n/**\n * Binary search approach O((n+m)*log(m))\n *\n * @param {number[]} spells\n * @param {number[]} potions\n * @param {number} success\n * @return {number[]}\n */\nvar successfulPairs = function (spells, potions, success) {\n        const pairs = [];\n        potions.sort((a, b) => a - b);\n        const spellsLength = spells.length;\n        const potionsLength = potions.length;\n\n        for (let i = 0; i < spellsLength; i++) {\n            let count = 0;\n            // binary search\n            let left = 0;\n            let right = potionsLength - 1;\n            while (left <= right) {\n                // const mid = Math.floor((left + right) / 2);\n                const mid = (left + right) >> 1;\n                if (spells[i] * potions[mid] >= success) {\n                    right = mid - 1;\n                } else {\n                    left = mid + 1;\n                }\n            }\n            count = potionsLength - left;\n            pairs.push(count);\n        }\n        return pairs;\n    };\n```\n\n```php []\nclass Solution\n{\n    /**\n     * @param Integer[] $spells\n     * @param Integer[] $potions\n     * @param Integer $success\n     * @return Integer[]\n     */\n    function successfulPairs(array $spells, array $potions, int $success): array {\n        $pairsResult = [];\n        $potionsCount = count($potions);\n        $spellsCount = count($spells);\n        sort($potions);\n        // binary search\n        for ($i = 0; $i < $spellsCount; $i++) {\n            $left = 0;\n            $right = $potionsCount - 1;\n            while ($left <= $right) {\n                $mid = ($left + $right) >> 1;\n                if ($spells[$i] * $potions[$mid] >= $success) {\n                    $right = $mid - 1;\n                } else {\n                    $left = $mid + 1;\n                }\n            }\n            $pairsResult[$i] = $potionsCount - $left;\n        }\n        return $pairsResult;\n    }\n}\n```\n\n```javascript []\n/**\n * Binary search approach with  with small optimization\n *\n * @param {number[]} spells\n * @param {number[]} potions\n * @param {number} success\n * @return {number[]}\n */\nvar successfulPairs = function (spells, potions, success) {\n        const pairs = [];\n        potions.sort((a, b) => a - b);\n        const spellsLength = spells.length;\n        const potionsLength = potions.length;\n\n        let maxSpellValueWithZeroSuccess = 0; // Optimize -  max value of a spell that will never be successful\n\n        for (let i = 0; i < spellsLength; i++) {\n            let count = 0;\n            if (spells[i] > maxSpellValueWithZeroSuccess) {\n                // binary search\n                let left = 0;\n                let right = potionsLength - 1;\n                while (left <= right) {\n                    const mid = (left + right) >> 1;\n                    if (spells[i] * potions[mid] >= success) {\n                        right = mid - 1;\n                    } else {\n                        left = mid + 1;\n                    }\n                }\n                count = potionsLength - left;\n                if (count == 0) maxSpellValueWithZeroSuccess = spells[i];\n            }\n            pairs.push(count);\n        }\n        return pairs;\n    };\n```\n\n##### Thanks for reading! If you have any questions or suggestions, please leave a comment below. I would love to hear your thoughts! \uD83D\uDE0A\n### **Please upvote if you found this post helpful! \uD83D\uDE4F**
['Binary Search', 'PHP', 'JavaScript']