力扣算法面试150题——二分查找——个人笔记

第一题

35. 搜索插入位置https://leetcode.cn/problems/search-insert-position/

题目内容

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

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

示例 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

思路

这是一道简单难度的题，要求用复杂度Ologn的算法其实就是暗示二分查找。二分的模版有两种，一种是左闭右开，另一种是左闭右闭。在写题目的时候发现大部分都可以转换。

二分的核心就是说，我能不能通过写一行if，将需要查找的范围缩小一半？

左闭右开——相当于[left , right)

left = 0 right = len while left < right: mid = (left + right) // 2 ... if ...: left = mid + 1 if ...: right = mid

左闭右闭——相当于[left , right]

left = 0 right = len - 1 while left <= right: mid = (left + right) // 2 ... if ...: left = mid + 1 if ...: right = mid - 1

代码

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

第二题

74. 搜索二维矩阵https://leetcode.cn/problems/search-a-2d-matrix/

题目内容

给你一个满足下述两条属性的m x n整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数target，如果target在矩阵中，返回true；否则，返回false。

示例1： 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true

思路

这题可以用二分来实现，一开始的时候没有用完全展开后的二分做，也能过，这边先记录两种做法

代码

方法一

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: if target > matrix[-1][-1] or target < matrix[0][0]: return False n = len(matrix) # 相当于先锁定行 for i in range(n): tmp = matrix[i] if target <= tmp[-1]: break # 再在特定的行中去做二分 left = 0 right = len(tmp) while left < right: mid = (left + right) // 2 if tmp[mid] == target: return True elif tmp[mid] < target: left = mid + 1 else: right = mid return False

方法二

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: # 完全展开后做二分 r = len(matrix) c = len(matrix[0]) left = 0 right = r * c - 1 while left <= right: mid = (left + right) // 2 # 这里的[][]需要注意，一开始写错了 if matrix[mid//c][mid % c] == target: return True elif matrix[mid//c][mid % c] > target: right = mid - 1 else: left = mid + 1 return False

第三题

162. 寻找峰值https://leetcode.cn/problems/find-peak-element/

题目内容

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设nums[-1] = nums[n] = -∞。

你必须实现时间复杂度为O(log n)的算法来解决此问题。

示例 1： 输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。 示例 2： 输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。

思路

可以把这道题想象成爬山，当mid < mid + 1的时候，就是上坡，那么峰值一定在右边，如果mid > mid + 1的时候，就是下坡，那么峰值一定在mid的左边。这题和之前的寻找target不一样，虽然同样是二分，但是这里需要用左闭右开区间（因为涉及到mid 与mid + 1的比较，会遇到边界问题）来实现，因为mid也有可能是答案，需要不断的二分，最终当循环结束时，left 和 right 处于一种“夹击”峰值的最终状态，因此最后返回left或right都可以（题目说只要是峰值即可）。

为什么这题用左闭右开？（1）while left < right的时候，取不到等号，导致left 永远比right小，因此mid永远达不到right，既然mid不是最后一个，那么mid + 1就永远不会越界；（2）在找峰值时，如果nums[mid] > nums[mid+1]，说明mid处于下坡，mid本身可能就是峰值，或者峰值在左边。左闭右开通常写成right = mid。这表示 mid 可能是答案，需要将它留在区间里继续查。

代码

class Solution: def findPeakElement(self, nums: List[int]) -> int: left = 0 right = len(nums) - 1 # 左闭右开写法 while left < right: mid = (left + right) // 2 if nums[mid] < nums[mid + 1]: left = mid + 1 elif nums[mid] > nums[mid + 1]: right = mid # [left, right) return left

第四题

33. 搜索旋转排序数组https://leetcode.cn/problems/search-in-rotated-sorted-array/

题目内容

整数数组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。

你必须设计一个时间复杂度为O(log n)的算法解决此问题。

示例 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

思路

Ologn 暗示了使用二分算法，使用左闭右闭区间，因为这道题的性质，相当于我每一次取的mid都会将列表划分为两部分。至少有一部分是升序的！于是利用这个特性，每次判断target是否在升序区间内，若在，则边界向升序区间靠拢，若不在，则边界向反方向靠拢。

这道题乍看之下发现很难写出这样一条if语句，每次将范围切掉一半，例如[4,5,6,1,2,3],target = 4,若是不利用升序特性的话，我第一步求出了mid = 2 nums[mid] = 6，但是我并不知道4在哪里啊，它有可能在左边也有可能在右边（5,6,1,2,3,4），我怎么才能写left和right的修改语句了，发现无从下手。因此需要例如升序属性（至少有一侧是升序的来判断，这样不管target在不在升序区间内，都可以修改left或right了）

其实本质还是判断target在mid的哪边，然后修改left或者right，让mid尽可能向target靠拢，若最终while循环都没有找到，则说明列表里不存在target。

代码

class Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 # 左闭右闭区间 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # 左边是升序的 if nums[left] <= nums[mid]: # 然后看target是否在升序区间内 if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 # 反之，右侧是升序的 else: # 然后看target是否在升序区间内 if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1

第五题

34. 在排序数组中查找元素的第一个和最后一个位置https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

题目内容

给你一个按照非递减顺序排列的整数数组nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值target，返回[-1, -1]。

你必须设计并实现时间复杂度为O(log n)的算法解决此问题。

示例 1： 输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4] 示例 2： 输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1] 示例 3： 输入：nums = [], target = 0 输出：[-1,-1]

思路

相当于做两次二分查找，第一次查找最左边的target，第二次查找最右边的target，模版基本不变，只不过再最终nums[mid] == target，先暂存当前的mid（用一个ans存储），之后继续修改left或right，确认更左侧或更右侧是否还有target值，若有则更新ans，若无就直接返回最新的ans，直到left > right，接着返回ans（ans初始值为-1，若列表中不存在target，则直接返回-1），因为比较乱，所以可以封装成两个内部函数来实现。

代码

class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # 搜索左边target def searchLeft(): left = 0 right = len(nums) - 1 ans = -1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: ans = mid right = mid - 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return ans # 搜索右边target def searchRight(): left = 0 right = len(nums) - 1 ans = -1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: ans = mid left = mid + 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return ans return [searchLeft(), searchRight()]

第六题

153. 寻找旋转排序数组中的最小值https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

题目内容

已知一个长度为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，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

你必须设计一个时间复杂度为O(log n)的算法解决此问题。

示例 1： 输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。 示例 2： 输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。 示例 3： 输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

思路

这道题和第四题很相似，都是同一类型的题目，需要旋转后的列表进行判断，且利用左侧和右侧部分至少一侧为升序的特性。但是这里注意，只需要和右侧比就可以了，如果if 条件里写和左侧比较，则需要考虑更多的情况，if 判断右侧是否为升序，若是，则先用当前的mid值更新最小值（初始化正无穷大），然后收缩right，继续去左边搜索看有没有更小值。同理若左侧为升序，则left就是最小值，再收缩左边界，去看右边有没有更小的。

代码

class Solution: def findMin(self, nums: List[int]) -> int: left = 0 right = len(nums) - 1 minnum = float('inf') while left <= right: mid = (left + right) // 2 # 和右边比较，判断右侧是不是升序的 # 若右侧升序，则mid就是最小值 if nums[mid] <= nums[right]: minnum = min(minnum, nums[mid]) # 下一轮再看mid 左边 right = mid - 1 # 若右侧不升序,则说明左侧升序 else: minnum = min(minnum, nums[left]) left = mid + 1 return minnum

第七题

4. 寻找两个正序数组的中位数https://leetcode.cn/problems/median-of-two-sorted-arrays/

题目内容

给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为O(log (m+n))。

示例 1： 输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2 示例 2： 输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

思路

本题的难度较大，属于困难题。先记录思路。这道题的难点在于，以前是一个已经排序好的数组，二分查找切，而现在是两个排好序的数组，如何实现二分的切？

这道题的关键点在于对中位数的理解，中位数实际就是将两个数组各切一刀，使得原本两个数组变成左边部分和右边部分，需要确保只控制较短的那个数组，因为另外一个长的数组的左边长度可以通过计算得出，具体来说就是，两个列表各切一刀，变成了1的左和1的右。2的左和2的右。一共4块。且1的左+ 2的左长度是固定的，1左+ 1右 = 总长度的一半

接着来到第二步，就是通过判断nums1的左、右，以及nums2的左、右的最大值和最小值，来更新left和right，具体来说就是两种情况（1）nums1的左最后一个数 > nums2的右第一个数，那么说明这一刀切的偏右了，更新right，（2）nums2的左最后一个数 > nums1的右第一个数，那么说明nums2的这一刀切的偏右了，与之对应的就是nums1的这一刀切的偏左了，需要更新left。

最终根据总长度是奇数还是偶数来判断对中位数的处理，若为奇数则直接输出中间值，若为偶数则需要计算。

代码

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: # 手动操作确保更短的那个列表作为nums1 if len(nums1)>len(nums2): nums1, nums2 = nums2, nums1 left = 0 right = len(nums1) # 这里不能减1，因为末尾也可以被切 # 左侧长度 lenleft = (len(nums1) + len(nums2) + 1) // 2 while left <= right: cut1 = (left + right) // 2 cut2 = lenleft - cut1 # 记录四个关键值 # nums1的左侧最大值 L1max = nums1[cut1 - 1] if cut1 > 0 else float('-inf') # nums2的左侧最大值 L2max = nums2[cut2 - 1] if cut2 > 0 else float('-inf') # nums1的右侧最小值 R1min = nums1[cut1] if cut1 < len(nums1) else float('inf') # nums2的右侧最小值 R2min = nums2[cut2] if cut2 < len(nums2) else float('inf') # 根据切分情况来更新left或right # 切的不好有两种可能 if L1max > R2min: right = cut1 - 1 # nums2切多了说明nums1切少了，因为cut1 + cut2的总和是不变的 elif L2max > R1min: left = cut1 + 1 # 如果能进入else，则说明当前切的没有问题 else: # 开始计算中位数，若为偶数，则需要额外计算 if (len(nums1) + len(nums2)) % 2 == 0: return float((max(L1max, L2max) + min(R1min, R2min)) / 2) else: return float(max(L1max,L2max))