LeetCode75学习计划-二分查找

算法解题思路很多会借鉴于题解区，如果侵权请联系删除。

本章节知识点为二分查找。

猜数字大小

题目标签：

• 二分查找

题目难度： Easy

题目描述：

猜数字游戏的规则如下：

• 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
• 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

• -1：我选出的数字比你猜的数字小 pick < num
• 1：我选出的数字比你猜的数字大 pick > num
• 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

返回我选出的数字

解题思路：

• 按照正常的二分查找逻辑走即可

代码实现：

func guessNumber(n int) int {
    left := 1
    right := n
    for left < right {
        mid := (left + right) / 2
        if guess(mid) <= 0 {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

咒语和药水的成功对数

题目标签：

• 二分查找
• 数组

题目难度： Medium

题目描述：

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

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

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

解题思路：

代码实现：

func successfulPairs(spells []int, potions []int, success int64) []int {
    // 药水按照强度排序
    sort.Ints(potions)
    pairs := make([]int, len(spells))
    // 循环每一个咒语，依次计算可以成功的组合数目
    for i, x := range spells {
        // 查找不满足结果的数据的下标，然后用总数减去就是满足的
        pairs[i] = len(potions) - sort.SearchInts(potions, (int(success)-1)/x + 1)
    }
    return pairs
}

寻找峰值

题目标签：

• 二分查找
• 数组

题目难度： Medium

题目描述：

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

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

解题思路：

• 最大值一定是一个峰值元素，所以遍历找最大值即可

代码实现：

func findPeakElement(nums []int) int {
  // 最大值一定是一个峰值元素，所以遍历找最大值即可
  res := 0
  for i, v := range nums {
    if v > nums[res] {
      res = i
    }
  }
  return res
}

爱吃香蕉的珂珂

题目标签：

• 二分查找
• 数组

题目难度： Medium

题目描述：

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

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

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

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

代码实现：

func minEatingSpeed(piles []int, h int) int {
  // 最大的一堆香蕉的数量
  max := 0
  for _, pile := range piles {
    if pile > max {
      max = pile
    }
  }
  return 1 + sort.Search(max - 1, func(speed int) bool {
    speed ++
    time := 0
    for _, pile := range piles {
      time += (pile + speed - 1) / speed
    }
    return time <= h
  })
}