68.查找插入位置
难度简单
给定一个排序的整数数组 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
69.山峰数组的顶部
难度简单
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
70.排序数组中只出现一次的数字
难度中等
给定一个只包含整数的有序数组 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]
71.按权重生成随机数
难度中等
给定一个正整数数组 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
72.求平方根
难度简单
给定一个非负整数 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
73.狒狒吃香蕉
难度中等
狒狒喜欢吃香蕉。这里有 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
