思路

首先需要确定能否使用二分。对于二分问题而言，二分答案需要保持单调性，但数组并不一定需要保持单调性。

第二步确定问题需要定位的位置，例如寻找第一个大于等于target的位置或最后一个大于等于target的位置。

第三步确定左右边界。

在排序数组中查找元素的第一个和最后一个位置

• 对于本题而言，数组单调可以使用二分查找
• 需要查找的是第一个大于等于target的位置
• 我常使用的是左闭右开，所以下面的答案都使用的是左闭右开模版。左边界明显为0，右边界为数组长度n。

func searchRange(nums []int, target int) []int {


    var s1 func(target int)int

    s1 = func(target int)int{
       l,r := 0,len(nums) //定义左右边界
    for l < r{  //确定终止位置
        mid := l+(r-l)/2 //防止溢出
        if nums[mid] >= target{ //找到第一个大于等于的位置
            r = mid
        }else{
            l = mid+1
        }
    }
    return r
    }

    start := s1(target)

    if start == len(nums) || nums[start] != target{
        return []int{-1,-1}
    }
    end := s1(target+1)-1
    return []int{start,end}
}

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

思路

• 对于potions而言，显然越大越容易成立，越小越不成立。具有二分性质

• 本题也可以找到第一个大于等于target的位置，再用potions长度减去即可获得后方的长度

• 左边界为0，右边界为数组长度。

func successfulPairs(spells []int, potions []int, success int64) []int {

    sort.Ints(potions)

    for i,x := range spells{
        l,r := 0,len(potions)

        for l < r{
            m := l+(r-l)/2

            if int64(x*potions[m]) >= success{
                r = m
            }else{
                l = m+1
            }
        }
        spells[i] = len(potions)-l
    }
    return spells



    return spells
}

2563. 统计公平数对的数目

思路

• 这题显然具有单调性，可以使用二分

• 这题可以分为两个部分，第一部分找到第一个大于等于lower的位置，第二部分是找到最后一个小于等于upper的位置，第二部分也可以转换成第一个大于等于upper+1的位置

• 左边界显然继续为0，右边界为数组长度

func countFairPairs(nums []int, lower int, upper int) (res int64) {
    sort.Ints(nums)

    var s1 func(n []int,target int) int

    s1 = func(n []int,target int) int {
        l, r := 0, len(n)
        for l < r {
            mid := l + (r-l)/2
            if n[mid] >= target {
                r = mid
            } else {
                l = mid + 1
            }
        }
        return r
    }
    fmt.Println(nums)
    for i := 0; i < len(nums); i++ {
        p,q := s1(nums[i+1:],upper-nums[i]+1),s1(nums[i+1:],lower-nums[i]) //数组会不断变小
   
        res += int64(p-q)
    }
    return 
}

875. 爱吃香蕉的珂珂

思路

• 对于最小速度k而言，明显具有单调性。大的能成，小的不一定能成

• 这题需要找到第一个大于等于target的位置

• 左边界为1，右边界为piles中的最大值。

func minEatingSpeed(piles []int, h int) int {
    l,r := 1,slices.Max(piles)

    for l < r{
        m := l+(r-l)/2
        cnt := 0
        for _,x := range piles{
            cnt += (x+m-1)/m
        }

        if cnt > h{ //大于边界时l 往左边移动，反之往右
            l = m+1
        }else{
            r = m
        }
    }
    return l
}

2187. 完成旅途的最少时间

思路

• 同上，答案具有单调性

• 需要找到第一个大于等于target的位置

• 左边界为排列后的最快速度，右边界为最快速乘以趟数

func minimumTime(time []int, totalTrips int) int64 {
    sort.Ints(time)
    l,r := time[0], totalTrips*time[0]

    for l < r{
        m := l+(r-l)/2
        cnt := 0
        for _,x := range time{
            cnt += m/x
        }

        if cnt >= totalTrips{
            r = m
        }else{
            l = m+1
        }
    }
    return int64(l)
}

2861. 最大合金数

思路

• 单调性同上

• 需要找到第一个大于等于的位置，若check满足则左边界变为mid+1，不满足则右边界为mid

• 左边界为0，右边界为budget+1

func maxNumberOfAlloys(n int, k int, budget int, composition [][]int, stock []int, cost []int) int {
    check := func (target int) bool { // target 是我们想要制造的合金数量
        for _, machine_i := range composition { // 选择使用第 i 台机器
            remain := budget // 预算
            for i, v := range machine_i { // v 是制造该合金需要该类金属的数量
                need := max(0, v*target-stock[i]) // 需要购买 i 类金属的数量, (该数不能小于 0)
                remain -= need*cost[i] // 买这些金属需要花的钱
            }
            if remain >= 0 {
                return true
            }
        }
        return false
    }

    l, r := 0, int(2e8)+1 // 题目很坑, 说好的数据范围到 1e8, 结果给到 2e8
    for l < r {
        mid := l+(r-l)>>1
        if check(mid) { // mid 作为想要制造和合金数, 如果符合, 就让 l = mid, l 即为答案
            l = mid+1
        } else {
            r = mid
        }
    }
    return l-1
}