[Binary Search, Medium] Successful Pairs of Spells and Potions

https://leetcode.com/problems/successful-pairs-of-spells-and-potions/description/?envType=study-plan-v2&envId=leetcode-75

O(n^2) 방식으로 풀면 엄청나게 느리겠지만 할 수는 있겠다.
그러나 이분탐색 카테고리로 분류된 만큼 O(n log n)으로 풀어야 하겠다.

처음에는 이분탐색으로 어쩌라는거지 싶었는데

spells 고정 순회하되 potions 배열을 애초에 정렬해두면 될 것 같다고 생각
-> 각 spell마다 potions에 대한 이분탐색, 적절한 인덱스를 찾아서 총 길이에서 해당 인덱스를 빼면 success가 가능한 조합의 갯수만큼이 될 듯

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        
        Arrays.sort(potions);
        int n = spells.length;
        int m = potions.length;

        int[] result = new int[n];

        for (int i=0; i<n; i++) {
            int spell = spells[i];

            int start = 0;
            int end = m - 1;
            int successStartIndex = m;

            while (start <= end) {
                int mid = start + (end - start) / 2;
                long temp = (long) spell * potions[mid];

                if (temp >= success) {
                    successStartIndex = mid;
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }

            result[i] = m - successStartIndex;
        }
        return result;
    }
}