2300. 咒语和药水的成功对数

2300. 咒语和药水的成功对数

• 难度: medium
• 原始链接: https://leetcode.cn/problems/successful-pairs-of-spells-and-potions
• 标签: 二分查找

解法一: 二分查找

go

func successfulPairs(spells []int, potions []int, success int64) []int {
    sort.Ints(potions)
    ans := make([]int, len(spells))
    length := len(potions)
    for i, num := range spells {
        ans[i] = length - halfSearch(potions, int((success + int64(num) - 1) / int64(num)))
    }
    return ans
}

func halfSearch(nums []int, target int) int {
    left := 0 
    right := len(nums) - 1
    for left <= right {
        mid := ((right - left) >> 1) + left
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}