介绍
思想：
猜数字大小（数是1到10）：
- 猜
5——太小了 - 猜
7——太小了 - 猜
8——太小了 - 猜
9——恭喜，你猜对了！
二分的时间复杂度为O(log n)
思路
猜数字大小：
- 定义两个变量
l和r； - 用
mid（猜的数）保存l和r的中间值； - 假如小了，则把
l变成mid+1（去除左半部）； - 假如大了，则把
r变成mid-1（去除右半部）； - 假如对了，则返回
mid； - 重复第
2-5句。
二分查找库
bisect.bisect
bisect.bisect(nums, x)，nums是一个排好序的数组，x是一个整数，用处是获取把x插入nums中后（nums依然是排好序的），x所在的位置。
bisect.bisect_left
bisect.bisect_left(nums, x)，nums是一个排好序的数组，x是一个整数，用处是获取把x插入nums中后（nums依然是排好序的），x所在的位置（索引会尽量小）。
bisect.bisect_right
bisect.bisect_right(nums, x)，nums是一个排好序的数组，x是一个整数，用处是获取把x插入nums中后（nums依然是排好序的），x所在的位置（索引会尽量大）。
bisect.insort
bisect.insort(nums, x)，nums是一个排好序的数组，x是一个整数，用处是把x插入nums中后，nums依然是排好序的。
bisect.insort(nums, x)等价于nums.insert(bisect.bisect(nums, x), x)
题目单
二分搜索
| 题目编号 | 难度 | 题目 |
|---|---|---|
| 35 | 简单 | 搜索插入位置 |
| 69 | 简单 | x 的平方根 |
| 278 | 简单 | 第一个错误的版本 |
| 374 | 简单 | 猜数字大小 |
| 704 | 简单 | 二分查找 |
| 793 | 困难 | 阶乘函数后 K 个零 |
二分答案
| 题目编号 | 难度 | 题目 |
|---|---|---|
| 875 | 中等 | 爱吃香蕉的珂珂 |
| 475 | 中等 | 供暖器 |
| 1482 | 中等 | 制作 m 束花所需的最少天数 |
| 1870 | 中等 | 准时到达的列车最小时速 |
搜索插入位置
解法一：暴力法
加入并排序，再获取索引。
Python3
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
nums.append(target)
nums.sort()
return nums.index(target)时间复杂度为O(n log n)
解法二：二分查找
思路同猜数字大小：
- 定义两个变量
l和r； - 用
mid（猜的数）保存l和r的中间值； - 假如小了，则把
l变成mid+1（去除左半部）； - 假如大了，则把
r变成mid-1（去除右半部）； - 假如对了，则返回
mid； - 重复第
2-5句。
Python3
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return left时间复杂度为O(log n)
图解：
1 / 6
解法三：二分查找 II
利用库bisect。
Python3
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
return bisect.bisect_left(nums, target)时间复杂度为O(log n)
x 的平方根
解法一：暴力法
暴力尝试。
Python3
class Solution:
def mySqrt(self, x: int) -> int:
for i in range(x+2):
if i*i > x:
return i-1时间复杂度为O(n)
解法二：二分查找
思路同猜数字大小：
- 定义两个变量
l和r； - 用
mid（猜的数）保存l和r的中间值； - 假如小了，则把
l变成mid+1（去除左半部）； - 假如大了，则把
r变成mid-1（去除右半部）； - 假如对了，则返回
mid； - 重复第
2-5句。
Python3
class Solution:
def mySqrt(self, x: int) -> int:
l, r = 0, x+1
while l < r:
mid = (l+r)//2
if mid**2 <= x and x < (mid+1)**2:
return mid
if mid**2 <= x:
l = mid
else:
r = mid+1时间复杂度为O(log n)
解法三：数学
Python3
class Solution:
def mySqrt(self, x: int) -> int:
return int(x**0.5)时间复杂度为O(1)
第一个错误的版本
解法一：二分查找
猜数字大小的变形：
- 定义两个变量
l和r和res； - 用
mid（猜的数）保存l和r的中间值； - 假如正确的，则把
l变成mid+1（去除左半部），将res变成min(res, mid)； - 假如错误的，则把
r变成mid-1（去除右半部）； - 假如
l >= r，则返回res。 - 重复第
2-5句。
Python3
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
res = n
l, r = 1, n+1
while l < r:
mid = (l+r)//2
a = isBadVersion(mid)
if a:
res = min(res, mid)
r = mid
else:
l = mid+1
return res解法二：搞笑法——真正的一行【写着好玩】
Python3
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
return __bad__一行版：
Python3
class Solution:firstBadVersion = lambda self, n: __bad__猜数字大小
解法一：二分查找
- 定义两个变量
l和r； - 用
mid（猜的数）保存l和r的中间值； - 假如小了，则把
l变成mid+1（去除左半部）； - 假如大了，则把
r变成mid-1（去除右半部）； - 假如对了，则返回
mid； - 重复第
2-5句。
Python3
class Solution:
def guessNumber(self, n: int) -> int:
l, r = 1, n
while l <= r:
mid = (l + r) // 2
if guess(mid) == 0:
return mid
elif guess(mid) == -1:
r = mid - 1
elif guess(mid) == 1:
l = mid + 1解法二：搞笑法——真正的一行【写着好玩】
Python3
class Solution:
def guessNumber(self, n: int) -> int:
return __pick__一行版：
Python3
class Solution:guessNumber = lambda self, n: __pick__二分查找
解法：二分查找
思路同猜数字大小：
- 定义两个变量
l和r； - 用
mid（猜的数）保存l和r的中间值； - 假如小了，则把
l变成mid+1（去除左半部）； - 假如大了，则把
r变成mid-1（去除右半部）； - 假如对了，则返回
mid； - 假如
l > r，则返回-1； - 重复第2-6句。
Python3
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)-1
while l <= r:
mid = (l+r)//2
if nums[mid] == target:
return mid
elif nums[mid] < target:
l = mid+1
else:
r = mid-1
return -1阶乘函数后 K 个零
前言
我想大家都做过力扣的172. 阶乘后的零。
回想一下那道题：
题目描述
解题思路
Python3
给定一个整数 n，返回 n! 结果尾数中零的数量。解法一：数学+找规律
思路：
我们发现答案只可能是0或5。
通过下表（下表的结果都为0）找到规律：
| 5 | 11 | 17 | 23 | 29 | 30 |
|---|---|---|---|---|---|
| 36 | 42 | 48 | 54 | 60 | 61 |
| 67 | 73 | 79 | 85 | 91 | 92 |
| 98 | 104 | 110 | 116 | 122 | 123 |
| 129 | 135 | 141 | 147 | 153 | 154 |
| 规律如下： |
每列差都为31，如果将表扩大到长度为31，每列差就会都为156，如果将表扩大到长度为156，每列差就会都为781，以此类推。 |
|---|
所以，我们可以从大到小取模。（从61035156到31） |
但是，现在还是有6种情况，我们要找一个规律，规律如下： |
如果K是30则返回0，如果不是就判断它整除6的结果是否为5，是则返回0，不是则返回5。 |
|---|
代码：
Python3
Python3
class Solution:
def preimageSizeFZF(self, K: int) -> int:
for i in [61035156, 12207031, 2441406, 488281, 97656, 19531, 3906, 781, 156, 31]:
K %= i
if K == 30:
return 0
K %= 6
if K == 5:
return 0
return 5举例：
时间复杂度：
时间复杂度为O(1)。
解法二：数学+二分查找
思路：
我们发现f(N) ≤ N ≤ f(N)*7和f(N) ≤ f(N+M)，f(x)表示x阶乘后有多少个零，其中N, M ≥ 0。
流程如下：
- 定义变量
l和r，确定如果结果为f(N)=K，那么：l≤N≤r， - 如果
l<r则执行以下操作：
- 定义两个变量
l和r； - 定义变量
mid保存中间值； - 如果
f(mid) = K则返回5； - 如果
f(mid) < K则减去左半边； - 如果
f(mid) > K则减去右半边； - 如果
r >= l则返回0 - 重复2-6句。
代码：
Python3
class Solution:
def preimageSizeFZF(self, K: int) -> int:
a = lambda x: 0 if not x else a(x//5)+x//5
l, r = K, K*7+1
while l<r:
mid = (l+r)//2
p = a(mid)
if p == K:
return 5
elif p < K:
l = mid+1
else:
r = mid-1
return 0举例：
1 / 2
时间复杂度：
时间复杂度为。
爱吃香蕉的珂珂
解法：二分答案
枚举K，判断是否合法。（二分思想，如果太大则变小，如果太小则变大）
Python3
class Solution:
def minEatingSpeed(self, piles: List[int], H: int) -> int:
l, r = 1, max(piles)
res = 10**9
while l <= r:
mid = (l+r) >> 1
a = sum((i+mid-1)//mid for i in piles)
if a > H:
l = mid+1
else:
res = min(res, mid)
r = mid-1
return res供暖器
解法：二分答案
枚举最小加热半径，判断是否合法。（二分思想，如果太大则变小，如果太小则变大）
Python3
class Solution:
def minEatingSpeed(self, piles: List[int], H: int) -> int:
l, r = 1, max(piles)
res = 10**9
while l <= r:
mid = (l+r) >> 1
a = sum((i+mid-1)//mid for i in piles)
if a > H:
l = mid+1
else:
res = min(res, mid)
r = mid-1
return res制作 m 束花所需的最少天数
解法：二分答案
枚举需要等待的最少的天数，判断是否合法。（二分思想，如果太大则变小，如果太小则变大）
Python3
class Solution:
def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
if m*k > len(bloomDay):
return -1
l, r = 1, max(bloomDay)
res = 10**9
while l <= r:
mid = (l+r) >> 1
a = [i <= mid for i in bloomDay]
n = 0
c = 0
p = a[0]
for i in a:
if p == i:
c += 1
else:
if p:
n += c // k
p = i
c = 1
if p:
n += c // k
if n < m:
l = mid+1
else:
res = min(res, mid)
r = mid-1
return res准时到达的列车最小时速
解法：二分答案
枚举需要等待的最少的天数，判断是否合法。（二分思想，如果太大则变小，如果太小则变大）
Python3
class Solution:
def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
res = 10000001
l, r = 1, 10000000
while l <= r:
mid = (l+r)//2
if sum([ceil(i/mid) for i in dist[:-1]])+dist[-1]/mid <= hour:
res = min(res, mid)
r = mid-1
else:
l = mid+1
return -1 if res == 10000001 else res相关书籍
评论 (2)
