第8-10天打卡，附上学习链接
1 学习内容
1.1 基础概念
二分查找算法（Binary Search Algorithm），又称为折半查找、对数查找算法，是一种在有序数组中查找某一特定元素的搜索算法。
基本思想：先确定待查找元素所在的区间范围，再逐步缩小范围，直到找到或找不到该元素为止。
1.2 算法步骤
- 每次查找从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
- 如果该查找元素大于/小于中间元素，则在数组大于/小于中间元素的那一半中查找，而且同样从中间元素开始比较；
- 如果在某一步骤数组为空，则代表查找不到该元素。
1.3 举例推演
0704 二分查找 *：给定一个升序的数组nums和一个目标值target，返回target在数组中的位置，如果找不到，则返回-1。
样例1：输入为nums=[-1, 0, 3, 5, 9, 12]，target=9，输出为4；
样例2：输入为nums=[-1, 0, 3, 5, 9, 12]，target=2，输出为-1。
思路1：直接法。一旦在循环体中找到该需查找的元素，就直接返回结果。
该种思路适合解决简单题目，即查找的元素性质简单，数组中都是非重复元素，且等于不等于的情况易于比较。
class Solution:
def search(self, nnums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2 # // 2 表示向下取整
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
思路2：排除法。在循环体中排除目标元素一定不存在的区间。
该思路适合于解决复杂题目，如查找一个数组里可能不存在的元素，找边界问题可使用该思路。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
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
while left < right:
mid = left + (right - left + 1) // 2 # 向上取整
if nums[mid] > target:
right = mid - 1
else:
left = mid
return left if nums[left] == target else -1
2 练习题目
2.1 0374 猜数字大小 *
题目描述：每轮游戏，会从1到n随机选择一个数字；如果猜错了，会告诉是大了还是小了。可以通过调用一个预先定义好的接口int guess(int num)来获取猜测结果，返回值一共有3种可能的情况（-1,1或0），-1表示选出的数字比猜的数字小，即pick<num；1表示选出的数字比猜的数字大，即pick>num；0表示猜对了，即pick==num。返回我选出的数字。
样例1：输入为n=10，pick=6，输出为6；
样例2：输入为n=1， pick=1，输出为1；
样例3：输入为n=2，pick=1，输出为1；
样例4：输入为n=2，pick=2，输出为2。
解题思路：二分法。
class Solution:
def guessNumber(self, n: int) -> int:
left, right = 1, n
while left < right:
mid = (left + right) // 2
if guess(mid) <= 0:
right = mid
else:
left = mid + 1
return left
2.2 0035 搜索插入位置 *
题目描述：给定一个数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在数组中，返回它将会被按顺序插入的位置。
样例1：输入为nums=[1, 3, 5, 6]，target=5，输出为2；
样例2：输入为nums=[1, 3, 5, 6]，target=2，输出为1；
样例3：输入为nums=[1, 3, 5, 6]，target=7，输出为4；
样例4：输入为nums=[1, 3, 5, 6]，target=0，输出为0；
样例5：输入为nums=[1]，target=0，输出为0。
解题思路：在一个有序数组中找到第一个大于等于target的下标。
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
res = len(nums)
while left <= right:
mid = (left + right) // 2
if target <= nums[mid]:
res = mid
right = mid - 1
else:
left = mid + 1
return res
2.3 0069 Sqrt(x) *
题目描述：给一个非负整数x，计算并返回x的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。不允许使用任何内置指数函数和算符。 样例1：输入为x=4，输出为2； 样例2：输入为x=8，输出为2。解释：8的算术平方根是2.82842...，由于返回类型是整数，小数部分将被舍去。
解题思路：转化为寻找满足k2<=x的最大k值。二分查找，下界为0，上界粗略设定为x。每一步，通过比较中间元素mid的平方与x的大小关系，不断调整上下界的范围。
class Solution:
def mySqrt(self, x: int) -> int:
left, right, res = 0, x, -1
while left <= right:
mid = (left + right) // 2
if mid ** 2 <= x:
res = mid
left = mid + 1
else:
right = mid - 1
return res
时间复杂度：O(log(x))； 空间复杂度：O(1)。
2.4 0167 两数之和II - 输入有序数组 *
题目描述：给一个已按照非递减顺序排列的整数数组numbers，从数组中找出两个数满足相加之和等于目标数target。函数应该以长度为2的整数数组的形式返回这两个数的下标值。numbers的下标从1开始计数，所以答案数组应当满足1<=answer[0]<answer[1]<=numbers.length。可假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 样例1：输入为numbers=[2, 7, 11, 15]，target=9，输出为[2, 7]； 样例2：输入为numbers=[2, 3, 4]，target=6，输出为[1, 3]； 样例3：输入为numbers=[-1, 0]，target=-1，输出为[1, 2]。
解题思路：固定第一个数，在其右侧寻找第二个数，使得第二个数等于目标值减去第一个数。（之前有做过一次）。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
n = len(numbers)
for i in range(n):
low, high = i+1, n-1
while low <= high:
mid = (low + high) // 2
if numbers[mid] == target - numbers[i]:
return [i+1, mid+1]
elif numbers[mid] > target - numbers[i]:
high = mid - 1
else:
low = mid + 1
return [-1, -1]
时间复杂度：O(nlog(n))； 空间复杂度：O(1)。
2.5 1011 在D天送达包裹的能力 **
题目描述：传送带上的包裹必须在D天内从一个港口运送到另一个港口。传送带上的第i个包裹的重量为weights[i]。每一天，都会按照重量的顺序往传送带上装载包裹。装载的重量不会超过船的最大运载重量。返回能在D天内将传送带上的所有包裹送达的船的最低运载能力。 样例1：输入为weights=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，D=5，输出为15；解释：第1天是1,2,3,4,5；第2天是6,7；第3天是8；第4天是9；第5天是10，所以最低载重为15。 样例2：输入为weights=[3, 2, 2, 4, 1, 4]，D=3，输出为6；解释：第1天是3,2；第2天是2,4；第3天是1,4；所以最低载重为6。 样例3：输入为weights=[1, 2, 3, 1, 1]，D=4，输出为3。解释：第1天是1；第2天是2；第3天是3；第4天是1,1；所以最低载重是3。
解题思路：二分查找转化为判定问题。存在一个运载能力的下限xans，使得x>=xans时，可以在days天运送完，反之无法运送完所有包裹。因为有顺序运载，连续安排在同一天进行运送。当这批包裹的重量大于运载能力x时，就需要将最后一个包裹拿出来，安排在新的一天，并继续往下遍历。当遍历完整个数组后，就得到了最少需要运送的天数。使用最少需要运送的天数与days进行比较，小于等于days时，忽略二分的右半部分区间；当其大于days时，就忽略二分的左半部分区间。
class Solution:
时间复杂度：O(nlog(sum(w)))； 空间复杂度：O(1)。
2.6 0278 第一个错误的版本 *
题目描述：每个版本的产品都是基于之前的版本开发，因此错误的版本之后的所有版本都是错误的。假设有n个版本[1, 2, ..., n]，找出导致之后版本出错的第一个错误版本。可以调用bool isBadVersion(version)接口来判断版本号version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。应该尽量减少对调用API的次数。 样例1：输入为n=5， bad=4，输出为4；解释：调用isBadVerison(3)->false；调用(4)->true；调用(5)->true。所以4是第一个错误的版本。 样子2：输入为n=1，bad=1，输出为1。
解题思路：左右初始化为1和n，从中间开始二分查找。
# 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
"""
left, right = 1, n
while left < right:
mid = (left + right) // 2
if isBadVersion(mid):
right = mid
else:
left = mid + 1
return left
时间复杂度：O(log(n))； 空间复杂度：O(1)。
2.7 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。 样例1：输入为nums=[4, 5, 6, 7, 0, 1, 2]，target=0，输出4； 样例2：输入为nums=[4, 5, 6, 7, 0, 1, 2]，target=3，输出为-1； 样例3：输入为nums=[1]，target=0，输出为-1。
解题思路：二分查找适用于有序数组。将数组从中间分开，肯定有一部分是有序的。首先mid分割，查看[left, mid]和[mid+1, right]哪个部分是有序的，根据有序的部分改变二分查找的上下界，根据有序的部分判断target在不在这个部分。
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
left, right = 0, len(nums)-1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]:
if nums[0] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[-1]:
left = mid + 1
else:
right = mid - 1
return -1
时间复杂度：O(log(n))； 空间复杂度：O(1)。
2.8 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，它原来是一个升序排列的数组，并进行了上述的多次旋转。找出并返回数组中的最小元素。 样例1：输入为nums=[3, 4, 5, 1, 2]，输出为1； 样例2：输入为nums=[4, 5, 6, 7, 0, 1, 2]，输出为0； 样例3：输入为nums=[11, 13, 15, 17]，输出为11。
解题思路：考虑数组中的最后一个元素x，在最小值右侧的元素，值一定都严格小于x；左侧一定都严格大于x。二分查找，左边界为low，右边界为high，区间的中点为pivot，最小值在该区间内。将中点元素与右边界元素相比。 （1）中点元素<右边界元素，则中点在最小值的右侧，可以忽略二分查找的右半部分； （2）中点元素>右边界元素，则中点在最小值的左侧，可以忽略二分查找的左半部分； 因为数组不包含重复元素，且当前的长度不为1，则不会和high重合。如果长度为1，可以结束二分查找。
class Solution:
def findMin(self, nums: List[int]) -> int:
low, high = 0, len(nums)-1
while low < high:
pivot = (low + high) // 2
if nums[pivot] < nums[high]:
high = pivot
else:
low = pivot + 1
return nums[low]
时间复杂度：O(log(n))； 空间复杂度：O(1)。
