当前位置： 首页 > article >正文

golang算法二分查找

article 2025/3/13 20:46:19

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

func searchRange(nums []int, target int) []int {
    l,r:=0,len(nums)-1
    mid:=0
    for l<=r{
        mid=(r-l)>>2+l
        if nums[mid]==target{
            break
        }else if nums[mid]<target{
            l=mid+1
        }else{
            r=mid-1
        }
    }
    l=mid
    r=mid
    if mid<0||mid>len(nums)-1{
        return []int{-1,-1}
    }
    if nums[mid]!=target{
        return []int{-1,-1}
    }
    for l>0&&nums[l]==nums[l-1]{
        l--
    }
    for r+1<len(nums)&&nums[r+1]==nums[r]{
        r++
    }
    return []int{l,r}
}

func search(nums []int,target int) int{
    l,r:=0,len(nums)-1
    for l<=r{
        mid:=(r-l)>>2+l
        if nums[mid]<target{
            l=mid+1
        }else{
            r=mid-1
        }
    }
    return l
}
func searchRange(nums []int, target int) []int {
    l:=search(nums,target)
    if l<0||l>len(nums)-1{
        return []int{-1,-1}
    }
    if nums[l]!=target{
        return []int{-1,-1}
    }
    return []int{l,search(nums,target+1)-1}
}

2529. 正整数和负整数的最大计数

给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。

换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。
注意：0 既不是正整数也不是负整数。

示例 1：

输入：nums = [-2,-1,-1,1,2,3]
输出：3
解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。
示例 2：

输入：nums = [-3,-2,-1,0,0,1,2]
输出：3
解释：共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。
示例 3：

输入：nums = [5,20,66,1314]
输出：4
解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。

提示：

1 <= nums.length <= 2000
-2000 <= nums[i] <= 2000
nums 按 非递减顺序 排列。

进阶：你可以设计并实现时间复杂度为 O(log(n)) 的算法解决此问题吗？

func search(nums []int,target int)int{
    l,r,mid:=0,len(nums)-1,0
    for l<=r{
        mid=(r-l)>>2+l
        if nums[mid]<target{
            l=mid+1
        }else{
            r=mid-1
        }
    }
    return l
}
func maximumCount(nums []int) int {
    l:=search(nums,0)
    l_nums,r_nums:=0,0
    if l<0||l>len(nums)-1{
        return len(nums)
    }
    if nums[l]<0{
        return max(l+1,len(nums)-l-1)
    }else if nums[l]>0{
        return max(l,len(nums)-l)
    }else{
        r:=l
        for l>0&&nums[l-1]==0{
            l--
        }
        for r<len(nums)-1&&nums[r+1]==0{
            r++
        }
        l_nums=l
        r_nums=len(nums)-r-1
        return max(l_nums,r_nums)
    }
}

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

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：

  • 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
  • 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
  • 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
    所以返回 [4,0,3] 。
    示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：

  • 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
  • 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
  • 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
    所以返回 [2,0,2] 。

提示：

n == spells.length
m == potions.length
1 <= n, m <= 105
1 <= spells[i], potions[i] <= 105
1 <= success <= 1010

func successfulPairs(spells []int, potions []int, success int64) []int {
    sort.Ints(potions)
    result:=[]int{}
    for i:=0;i<len(spells);i++{
        l,r:=0,len(potions)-1
        var target int64 =(success-1)/int64(spells[i])+1
        for l<=r{
            mid:=(r-l)>>2+l
            if int64(potions[mid])<target{
                l=mid+1
            }else{
                r=mid-1
            }
        }
        result=append(result,len(potions)-l)
    }
    return result
}

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

2563. 统计公平数对的数目

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

0 <= i < j < n，且
lower <= nums[i] + nums[j] <= upper

示例 1：

输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
输出：6
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。
示例 2：

输入：nums = [1,7,9,2,5], lower = 11, upper = 11
输出：1
解释：只有单个公平数对：(2,3) 。

提示：

1 <= nums.length <= 105
nums.length == n
-109 <= nums[i] <= 109
-109 <= lower <= upper <= 109

func countFairPairs(nums []int, lower int, upper int) int64 {
    sort.Ints(nums)
    var ans int64=0
    for i:=0;i<len(nums);i++{
        l:=sort.SearchInts(nums[:i],lower-nums[i])
        r:=sort.SearchInts(nums[:i],upper-nums[i]+1)
        ans+=int64(r-l)
    }
    return ans
}

275. H 指数 II

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。

请你设计并实现对数时间复杂度的算法解决此问题。

示例 1：

输入：citations = [0,1,3,5,6]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有3篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3 。
示例 2：

输入：citations = [1,2,100]
输出：2

提示：

n == citations.length
1 <= n <= 105
0 <= citations[i] <= 1000
citations 按 升序排列

func hIndex(citations []int) int {
    sort.Ints(citations)
    l,r:=0,len(citations)-1
    ans:=0
    for l<=r {
        mid:=(r-l)>>2+l
        ans=max(ans,min(citations[mid],len(citations)-mid))
        if citations[mid]<=len(citations)-mid{
            l=mid+1
        }else{
            r=mid-1
        }
    }
    return ans
}

875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

示例 1：

输入：piles = [3,6,7,11], h = 8
输出：4
示例 2：

输入：piles = [30,11,23,4,20], h = 5
输出：30
示例 3：

输入：piles = [30,11,23,4,20], h = 6
输出：23

提示：

1 <= piles.length <= 104
piles.length <= h <= 109
1 <= piles[i] <= 109

func minEatingSpeed(piles []int, h int) int {
    left:=1
    right:=slices.Max(piles)
    for left<=right{
        mid:=(right-left)>>2+left
        sum:=0
        for _,p:=range piles{
            sum+=((p-1)/mid)+1
        }
        if sum>h{
            left=mid+1
        }else{
            right=mid-1
        }
    }
    return left
}

2187. 完成旅途的最少时间

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。

每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

示例 1：

输入：time = [1,2,3], totalTrips = 5
输出：3
解释：

  • 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
    已完成的总旅途数为 1 + 0 + 0 = 1 。
  • 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
    已完成的总旅途数为 2 + 1 + 0 = 3 。
  • 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
    已完成的总旅途数为 3 + 1 + 1 = 5 。
    所以总共完成至少 5 趟旅途的最少时间为 3 。
    示例 2：

输入：time = [2], totalTrips = 1
输出：2
解释：
只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。

提示：

1 <= time.length <= 105
1 <= time[i], totalTrips <= 107

func minimumTime(time []int, totalTrips int) int64 {
    slices.Sort(time)
    l:=1
    r:=totalTrips*time[0]
    for l<=r{
        mid:=(r-l)>>2+l
        sum:=0
        for _,v:=range time{
            sum+=mid/v
        }
        if sum<totalTrips{
            l=mid+1
        }else{
            r=mid-1
        }
    }
    return int64(l)
}

2861. 最大合金数🪝

假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。

对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[i] 份 i 类型金属，而每购入一份 i 类型金属需要花费 cost[i] 的金钱。

给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。

所有合金都需要由同一台机器制造。

返回公司可以制造的最大合金数。

示例 1：

输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]
输出：2
解释：最优的方法是使用第 1 台机器来制造合金。
要想制造 2 份合金，我们需要购买：

  • 2 份第 1 类金属。
  • 2 份第 2 类金属。
  • 2 份第 3 类金属。
    总共需要 2 * 1 + 2 * 2 + 2 * 3 = 12 的金钱，小于等于预算 15 。
    注意，我们最开始时候没有任何一类金属，所以必须买齐所有需要的金属。
    可以证明在示例条件下最多可以制造 2 份合金。
    示例 2：

输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,100], cost = [1,2,3]
输出：5
解释：最优的方法是使用第 2 台机器来制造合金。
要想制造 5 份合金，我们需要购买：

  • 5 份第 1 类金属。
  • 5 份第 2 类金属。
  • 0 份第 3 类金属。
    总共需要 5 * 1 + 5 * 2 + 0 * 3 = 15 的金钱，小于等于预算 15 。
    可以证明在示例条件下最多可以制造 5 份合金。
    示例 3：

输入：n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5]
输出：2
解释：最优的方法是使用第 3 台机器来制造合金。
要想制造 2 份合金，我们需要购买：

  • 1 份第 1 类金属。
  • 1 份第 2 类金属。
    总共需要 1 * 5 + 1 * 5 = 10 的金钱，小于等于预算 10 。
    可以证明在示例条件下最多可以制造 2 份合金。

提示：

1 <= n, k <= 100
0 <= budget <= 108
composition.length == k
composition[i].length == n
1 <= composition[i][j] <= 100
stock.length == cost.length == n
0 <= stock[i] <= 108
1 <= cost[i] <= 100

func maxNumberOfAlloys(_, _, budget int, composition [][]int, stock, cost []int) (ans int) {
	mx := slices.Min(stock) + budget
	for _, comp := range composition {
		ans += sort.Search(mx-ans, func(num int) bool {
			num += ans + 1
			money := 0
			for i, s := range stock {
				if s < comp[i]*num {
					money += (comp[i]*num - s) * cost[i]
					if money > budget {
						return true
					}
				}
			}
			return false
		})
	}
	return
}

2439. 最小化数组中的最大值🪝

给你一个下标从 0 开始的数组 nums ，它含有 n 个非负整数。

每一步操作中，你需要：

选择一个满足 1 <= i < n 的整数 i ，且 nums[i] > 0 。
将 nums[i] 减 1 。
将 nums[i - 1] 加 1 。
你可以对数组执行 任意 次上述操作，请你返回可以得到的 nums 数组中 最大值 最小 为多少。

示例 1：

输入：nums = [3,7,1,6]
输出：5
解释：
一串最优操作是：

  1. 选择 i = 1 ，nums 变为 [4,6,1,6] 。
  2. 选择 i = 3 ，nums 变为 [4,6,2,5] 。
  3. 选择 i = 1 ，nums 变为 [5,5,2,5] 。
    nums 中最大值为 5 。无法得到比 5 更小的最大值。
    所以我们返回 5 。
    示例 2：

输入：nums = [10,1]
输出：10
解释：
最优解是不改动 nums ，10 是最大值，所以返回 10 。

func minimizeArrayValue(nums []int) int {
	return sort.Search(slices.Max(nums), func(limit int) bool {
		extra := 0
		for i := len(nums) - 1; i > 0; i-- {
			extra = max(nums[i]+extra-limit, 0)
		}
		return nums[0]+extra <= limit
	})
}

2517. 礼盒的最大甜蜜度🪝

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。

商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。

返回礼盒的 最大 甜蜜度。

示例 1：

输入：price = [13,5,1,8,21,2], k = 3
输出：8
解释：选出价格分别为 [13,5,21] 的三类糖果。
礼盒的甜蜜度为 min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8 。
可以证明能够取得的最大甜蜜度就是 8 。
示例 2：

输入：price = [1,3,1], k = 2
输出：2
解释：选出价格分别为 [1,3] 的两类糖果。
礼盒的甜蜜度为 min(|1 - 3|) = min(2) = 2 。
可以证明能够取得的最大甜蜜度就是 2 。
示例 3：

输入：price = [7,7,7,7], k = 2
输出：0
解释：从现有的糖果中任选两类糖果，甜蜜度都会是 0 。

提示：

2 <= k <= price.length <= 105
1 <= price[i] <= 109

func maximumTastiness(price []int, k int) int {
    slices.Sort(price)
    return sort.Search((price[len(price)-1]-price[0])/(k-1), func(d int) bool {
        d++ // 二分最小的 f(d+1) < k，从而知道最大的 f(d) >= k
        cnt, pre := 1, price[0]
        for _, p := range price[1:] {
            if p >= pre+d {
                cnt++
                pre = p
            }
        }
        return cnt < k
    })
}

http://www.kler.cn/a/583212.html

相关文章：

  • Qt开源控件库（qt-material-widgets）的编译及使用
  • 【原创】springboot+vue音乐教育培训管理系统设计与实现
  • 2.angular指令
  • AI驱动的数字供应链安全情报预警服务：云脉XSBOM
  • Token登录授权、续期和主动终止的方案(Redis+Token（非jwtToken）)
  • 点云深度学习系列：PVRCNN——point-voxel融合的分割模型
  • 攻防世界web：NewsCenter（含sqlmap基本参数讲解）
  • 引入其他 YML 配置源 —— Spring Boot 中的 `import` 功能
  • Axios简单说明，快速上手
  • 3.12-2 html
  • 电商数据分析 电商平台销售数据分析 电商平台数据库设计 揭秘电商怎么做数据分析
  • hadoop框架与核心组件刨析（五）ZOOKEEPER及选举深度刨析
  • llamaindex实现企业级RAG应用（一）
  • stm32-RTC时实时钟
  • C++复试笔记（二）
  • 下载文件，文件名乱码问题
  • Java高频面试之集合-10
  • 利用axios库的爬虫程序如何使用HTTP
  • 静态路由配置实验相关过程
  • 【Python】06、流程控制语句