二分查找-Python

• • 68.查找插入位置
  • 69.山峰数组的顶部
  • 70.排序数组中只出现一次的数字
  • 71.按权重生成随机数
  • 72.求平方根
  • 73.狒狒吃香蕉

难度简单

给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = 0, n
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid
        return left

难度简单

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        n = len(arr)
        left, right = 0, n
        while left < right:
            mid = left + (right - left) // 2
            if arr[mid] > arr[mid-1] and arr[mid] > arr[mid+1]:
                return mid
            elif arr[mid] < arr[mid-1]:
                right = mid
            elif arr[mid] < arr[mid+1]:
                left = mid + 1
        return left

难度中等

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            mid -= mid & 1
            if nums[mid] != nums[mid+1]:
                right = mid
            else:
                left = mid + 2
        return nums[left]

难度中等

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

class Solution:

    def __init__(self, w: List[int]):
        self.sum = w[:]
        for i in range(1, len(w)):
            self.sum[i] += self.sum[i-1]


    def pickIndex(self) -> int:
        random = choice(range(1, self.sum[-1]+1))
        # 判断random是否在self.sum(升序)里：（与68题思路一致）
        # 如果在，返回在self.sum里对应的索引
        # 如果不在，返回插入self.sum对应位置的索引
        left, right = 0, len(self.sum)-1
        if random < self.sum[0]:
            return 0
        while left < right:
            mid = left + (right - left) // 2
            if random > self.sum[mid]:
                left = mid + 1
            elif random < self.sum[mid]:
                right = mid
            else:
                return mid
        return left

难度简单

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

class Solution:
    def mySqrt(self, x: int) -> int:
        # 防止分母为0
        if x == 0:
            return 0
        left, right = 1, x
        while left < right:
            mid = left + (right-left)//2
            # mid**2 <= x < (mid+1)**2 防止溢出稍微改一下
            if mid <= x/mid and x / (mid+1) < (mid+1):
                return mid
            elif (mid+1) <= x / (mid+1):
                left = mid + 1
            elif x/mid < mid:
                right = mid
        return left

难度中等

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

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

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

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

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        # 1.二分查找先确定范围
        # 每小时最少要吃1个，最多要吃最大堆的香蕉个数
        # 由于下面的mid取不到max(piles)，所以这里➕1,不加的话就if语句特殊处理
        left, right = 1, max(piles)+1
        # 符合条件的K有多个，取最小的
        K = 10**9
        while left < right:
            mid = left + (right - left) // 2
            # 吃完用的小时数
            H = 0
            for i in piles:
                H += ceil(i/mid)
            if H > h:
                left = mid + 1
            else:
                right = mid
                K = min(K, mid)
        return K