1
/**
2
 * @param {number[]} spells
3
 * @param {number[]} potions
4
 * @param {number} success
5
 * @return {number[]}
6
 */
7
var successfulPairs = function (spells, potions, success) {
8
  let res = [];
9
  potions.sort((a, b) => b - a);
10
  let map = new Map();
11

12
  for (let i = 0; i < spells.length; i++) {
13
    if (!map.has(spells[i])) {
14
      let s = success / spells[i];
15
      let len = search(potions, s);
16
      res.push(len);
17
      map.set(spells[i], len);
18
    } else {
19
      let len = map.get(spells[i]);
20
      res.push(len);
21
    }
22
  }
23

24
  return res;
25
};
26

27
function search(potions, target) {
28
  let res = 0;
29
  let left = 0;
30
  let right = potions.length - 1;
31
  while (left <= right) {
32
    let mid = Math.floor((left + right) / 2);
33
    if (potions[mid] < target) {
34
      right = mid - 1;
35
    } else {
36
      left = mid + 1;
37
      res = mid + 1;
38
    }
39
  }
40

41
  return res;
42
}