本文章基于 Datewhale第31期组队学习
二分查找代码：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
# 在区间 [left, right] 内查找 target
while left <= right:
# 取区间中间节点
mid = (left + right) // 2
# 如果找到目标值，则直接返回中心位置
if nums[mid] == target:
return mid
# 如果 nums[mid] 小于目标值，则在 [mid + 1, right] 中继续搜索
elif nums[mid] < target:
left = mid + 1
# 如果 nums[mid] 大于目标值，则在 [left, mid - 1] 中继续搜索
else:
right = mid - 1
# 未搜索到元素，返回 -1
return -1
1.关于 left <= right 和 left < right:
- 如果判断语句为
left <= right，且查找的元素不存在，则while判断语句出界条件是left == right + 1，写成区间形式就是[right + 1, right]，此时待查找区间为空，待查找区间中没有元素存在，所以此时终止循环可以直接返回-1是正确的。 - 如果判断语句为
left < right，且查找的元素不存在，则while判断语句出界条件是left == right，写成区间形式就是[right, right]。此时区间不为空，待查找区间还有一个元素存在，并不能确定查找的元素不在这个区间中，此时终止循环返回-1是错误的。
比如说区间 [2, 2]，元素 2 就属于这个区间，此时终止循环，返回 -1 就漏掉了这个元素。
面对此种情况可以在返回的时候需要增加一层判断，判断 left 所指向位置是否等于目标元素，如果是的话就返回 left，如果不是的话返回 -1
此外，用 left < right 的话还有一个好处，就是退出循环的时候 left == right 成立，就不用判断应该返回 left 还是 right 了。
2. 二分查找两种思路
直接找
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
# 在区间 [left, right] 内查找 target
while left <= right:
# 取区间中间节点
mid = left + (right - left) // 2
# 如果找到目标值，则直接范围中心位置
if nums[mid] == target:
return mid
# 如果 nums[mid] 小于目标值，则在 [mid + 1, right] 中继续搜索
elif nums[mid] < target:
left = mid + 1
# 如果 nums[mid] 大于目标值，则在 [left, mid - 1] 中继续搜索
else:
right = mid - 1
# 未搜索到元素，返回 -1
return -1排除法
代码一：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
# 在区间 [left, right] 内查找 target
while left < right:
# 取区间中间节点
mid = left + (right - left) // 2
# nums[mid] 小于目标值，排除掉不可能区间 [left, mid]，在 [mid + 1, right] 中继续搜索
if nums[mid] < target:
left = mid + 1
# nums[mid] 大于等于目标值，目标元素可能在 [left, mid] 中，在 [left, mid] 中继续搜索
else:
right = mid
# 判断区间剩余元素是否为目标元素，不是则返回 -1
return left if nums[left] == target else -1
代码二：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
# 在区间 [left, right] 内查找 target
while left < right:
# 取区间中间节点
mid = left + (right - left + 1) // 2
# nums[mid] 大于目标值，排除掉不可能区间 [mid, right]，在 [left, mid - 1] 中继续搜索
if nums[mid] > target:
right = mid - 1
# nums[mid] 小于等于目标值，目标元素可能在 [mid, right] 中，在 [mid, right] 中继续搜索
else:
left = mid
# 判断区间剩余元素是否为目标元素，不是则返回 -1
return left if nums[left] == target else -1- 关于边界设置可以记忆为：只要看到
left = mid就向上取整。即：left = mid + 1和right = mid和mid = left + (right - left) // 2一定是配对出现的。right = mid - 1和left = mid和mid = left + (right - left + 1) // 2一定是配对出现的。
题目：
0704. ⼆分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
class Solution:
def search(self, nums: List[int], target: int) -> int:
length = len(nums)
l = 0
r = length - 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
0035. 搜索插⼊位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
输入: nums = [1,3,5,6], target = 5
输出: 2
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
length = len(nums)
l = 0
r = length - 1
while l <= r:
mind = (l + r)//2
if nums[mind] == target:
return mind
elif nums[mind] < target:
l = mind + 1
else :
r = mind - 1
return l
0374. 猜数字⼤⼩
猜数字游戏的规则如下：
每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。
输入：n = 10, pick = 6
输出：6
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num: int) -> int:
class Solution:
def guessNumber(self, n: int) -> int:
left, right = 1, n
while left <= right:
mid = (left + right) // 2
if not guess(mid):
return mid
elif guess(mid) == -1:
right = mid - 1
else:
left = mid + 1
0069. Sqrt(x)
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
输入：x = 4 输出：2
class Solution:
def mySqrt(self, x: int) -> int:
l = 0
r = x
while l <= r:
mid = (l + r)//2
m = mid * mid
n = (mid + 1) * (mid + 1)
if m <= x:
if n == x:
return mid + 1
elif n > x:
return mid
else:
l = mid + 1
else :
r = mid - 10167. 两数之和 II - 输⼊有序数组
给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l, r = 0, len(numbers) - 1
while l <= r:
if numbers[l] + numbers[r] == target:
return [l + 1, r + 1 ]
elif numbers[l] + numbers[r] < target:
l += 1
else:
r -= 11011. 在 D 天内送达包裹的能⼒
传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
笔者注：这题要不是在练习二分查找时所写我的第一反应时DP，后来发现DP会超时、、、
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
# 要不是这题在二分查找、、、、、、、、、
left = max(weights)
right = sum(weights) # 运量必然在 max(weights) 与 sum(weights) 之间
while left <= right:
mid = (left + right)//2
day, num = 1, 0
for i in weights:
num += i
if num > mid:
num = i
day += 1
if day > days: # 注意边界
left = mid + 1
elif day <= days: # 无法保证相等时是最小运量所在 所以改 right
right = mid - 1
return left
0278. 第⼀个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
l, r = 1, n
while l <= r:
mid = (l + r)//2
if isBadVersion(mid):
r = mid - 1
else:
l = mid + 1
return l
0033. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
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] < nums[r]: # mid 右边有序
if nums[mid] < target and nums[r] >= target: # 目标在有序中
l = mid + 1
else:
r = mid - 1
else: # mid 左边有序
if nums[mid] > target and nums[l] <= target: # 目标在有序中
r = mid - 1
else:
l = mid + 1
return -1
0153. 寻找旋转排序数组中的最⼩值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r)//2
if nums[mid] <= nums[r]:
r = mid # 最小值在 mid 左边 or mid 本身
else:
l = mid + 1 # 最小值必在 mid 右边
return nums[l]