当前位置： 首页 > news >正文

温州市建设小学大南网站,外链生成工具,建站平台 iis,吉林市建设官方网站1 二分法介绍 1.1 定义 二分查找又称折半查找、二分搜索、折半搜索等#xff0c;是一种在静态查找表中查找特定元素的算法。 所谓静态查找表#xff0c;即只能对表内的元素做查找和读取操作#xff0c;不允许插入或删除元素。 使用二分查找算法#xff0c;必须保证查找表中…1 二分法介绍 1.1 定义 二分查找又称折半查找、二分搜索、折半搜索等是一种在静态查找表中查找特定元素的算法。 所谓静态查找表即只能对表内的元素做查找和读取操作不允许插入或删除元素。 使用二分查找算法必须保证查找表中存放的是有序序列升序或者降序。换句话说存储无序序列的静态查找表除非先对数据进行排序否则不能使用二分查找算法。它针对的是一个有序的数据集合查找思想有点类似分治思想。每次都通过跟区间的中间元素对比将待查找的区间缩小为之前的一半直到找到要查找的元素或者区间被缩小为 0。下图对比了顺序查找和二分查找的不同 二分查找的最基本问题是在有序数组里查找一个特定的元素还可以应用在 在半有序旋转有序或者是山脉数组里查找元素确定一个有范围的整数需要查找的目标元素满足某个特定的性质。 二分查找算法的时间复杂度可以用 O(log2n)O(log_2n)O(log2​n) 表示nnn 为查找表中的元素数量底数 2 可以省略。和顺序查找算法的 O(n)O(n)O(n) 相比显然二分查找算法的效率更高且查找表中的元素越多二分查找算法效率高的优势就越明显。 1.2 二分法的三种写法

1. 模板一 class Solution(object):def search(self, nums: List[int], target: int) - int:# 特殊用例判断n len(nums)if n 0:return -1# 在 [left, right] 区间里查找targetleft, right 0, n - 1while left right:# 为了防止 left right 整形溢出写成如下形式# Python 使用 BigInteger所以不用担心溢出但还是推荐使用如下方式mid left (right - left) // 2if nums[mid] target:return midelif nums[mid] target:# 下一轮搜索区间[left, mid - 1]right mid - 1else:# 此时nums[mid] target# 下一轮搜索区间[mid 1, right]left mid 1return -1注意事项 许多刚刚写的朋友经常在写 left mid 1还是写 right mid - 1; 感到困惑一个行之有效的思考策略是永远去想下一轮目标元素应该在哪个区间里 如果目标元素在区间 [left, mid - 1] 里就需要设置设置 right mid - 1如果目标元素在区间 [mid 1, right] 里就需要设置设置 left mid 1 考虑不仔细是初学二分法容易出错的地方这里切忌跳步需要仔细想清楚每一行代码的含义。 二分查找算法是典型的「减治思想」的应用我们使用二分查找将待搜索的区间逐渐缩小以达到「缩减问题规模」的目的循环可以继续的条件是 while (left right)特别地当 left right 即当待搜索区间里只有一个元素的时候查找也必须进行下去mid (left right) // 2在 left right 整形溢出的时候mid 会变成负数回避这个问题的办法是写成 mid left (right - left) // 2。

2. 模板二 版本一 def search(nums: List[int], left: int, right: int, target: int) - int:while left right:# 选择中位数时下取整mid left (right - left) // 2if check(mid):# 下一轮搜索区间是 [mid 1, right]left mid 1else:# 下一轮搜索区间是 [left, mid]right mid# 退出循环的时候程序只剩下一个元素没有看到。# 视情况是否需要单独判断 left或者 right这个下标的元素是否符合题意版本二 def search(nums: List[int], left: int, right: int, target: int) - int:while left right:# 选择中位数时上取整mid left (right - left 1) // 2if check(mid):# 下一轮搜索区间是 [left, mid - 1]right mid - 1else:# 下一轮搜索区间是 [mid, right]left mid# 退出循环的时候程序只剩下一个元素没有看到。# 视情况是否需要单独判断 left或者 right这个下标的元素是否符合题意理解模板代码的要点 核心思想虽然模板有两个但是核心思想只有一个那就是把待搜索的目标元素放在最后判断每一次循环排除掉不存在目标元素的区间目的依然是确定下一轮搜索的区间特征while (left right):这里使用严格小于 表示的临界条件是当区间里的元素只有 2 个时依然可以执行循环体。换句话说退出循环的时候一定有 left right成立这一点在定位元素下标的时候极其有用在循环体中先考虑 nums[mid] 在满足什么条件下不是目标元素进而考虑两个区间 [left, mid - 1] 以及 [mid 1, right] 里元素的性质目的依然是确定下一轮搜索的区间 注意 1 先考虑什么时候不是解是一个经验在绝大多数情况下不易出错重点还是确定下一轮搜索的区间由于这一步不容易出错它的反面也就是 else 语句的部分就不用去考虑对应的区间是什么直接从上一个分支的反面区间得到进而确定边界如何设置根据边界情况看取中间数的时候是否需要上取整 注意 2 这一步也依然是根据经验建议先不要记住结论在使用这个思想解决问题的过程中去思考可能产生死循环的原因进而理解什么时候需要在括号里加 1 什么时候不需要在退出循环以后根据情况看是否需要对下标为 left 或者 right 的元素进行单独判断这一步叫「后处理」。在有些问题中排除掉所有不符合要求的元素以后剩下的那 1 个元素就一定是目标元素。如果根据问题的场景目标元素一定在搜索区间里那么退出循环以后可以直接返回 left或者 right。 以上是这两个模板写法的所有要点并且是高度概括的。请读者一定先抓住这个模板的核心思想在具体使用的过程中不断地去体会这个模板使用的细节和好处。只要把中间最难理解的部分吃透几乎所有的二分问题就都可以使用这个模板来解决因为「减治思想」是通用的。好处在这一小节的开篇介绍过了需要考虑的细节最少。 学习建议一定需要多做练习体会这两个模板的使用。 注意事项 先写分支再决定中间数是否上取整在使用多了以后就很容易记住只要看到 left mid 它对应的取中位数的取法一定是 mid left (right - left 1) // 2。

3. 模板三 def search(nums: List[int], left: int, right: int, target: int) - int:while left 1 right:# 选择中位数时下取整mid left (right - left) // 2if nums[mid] target:return midelif nums[mid] target:left midelse:right midif nums[left] target:return leftif nums[right] target:return rightreturn -1这一版代码和模板二没有本质区别一个显著的标志是循环可以继续的条件是 while (left 1 right):这说明在退出循环的时候一定有 left 1 right 成立也就是退出循环以后区间有 2 个元素即 [left, right]这种写法的优点是不用理解上一个版本在分支出现 left mid 的时候中间数上取整的行为缺点是显而易见的 while (left 1 right): 写法相对于 while (left right): 和 while (left right): 来说并不自然由于退出循环以后区间一定有两个元素需要思考哪一个元素才是需要找的即「后处理」一定要做有些时候还会有先考虑 left 还是 right 的区别。
   小结 模板一最好理解的版本但是在刷题的过程中需要处理一些边界的问题一不小心容易出错模板二强烈推荐掌握的版本应先理解思想再通过实际应用去体会这个模板的细节熟练使用以后就会觉得非常自然模板三可以认为是模板二的避免踩坑版本只要深刻理解了模板二模板三就不在话下。 实际应用中选择最好理解的版本即可。 这里有一个提示模板二考虑的细节最少可以用于解决一些相对复杂的问题。缺点是学习成本较高初学的时候比较容易陷入死循环建议大家通过多多使用并且尝试 debug找到死循环的原因进而掌握。 题解核心内容所有模板都一样不可以套模板而应该仔细看题解题的关键在认真读题分析清楚题目要找的答案需要满足什么性质。采用两边夹的方式每一轮把待搜索区间分成两个部分排除掉一定不是答案的区间最后左右指针重合的地方就是我们要找的元素。一定要分析清楚题目的意思分析清楚要找的答案需要满足什么性质。应该清楚模板具体的用法明白需要根据题意灵活处理、需要变通的地方不可以认为每一行代码都是模板规定死的写法不可以盲目套用、死记硬背。 2 常见题型 2.1 二分求下标在数组中查找符合条件的元素的下标 题库列表 题号链接704二分查找简单35搜索插入位置简单300最长上升子序列中等34在排序数组中查找元素的第一个和最后一个位置简单611有效三角形的个数436寻找右区间中等4寻找两个有序数组的中位数困难 2.2 完全有序

4. 二分查找         题目描述给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。

   lower_bound 返回最小的满足 nums[i] target 的 i

   如果数组为空或者所有数都 target则返回 len(nums)

   要求 nums 是非递减的即 nums[i] nums[i 1]# 闭区间写法

   def lower_bound(nums: List[int], target: int) - int:left, right 0, len(nums) - 1 # 闭区间 [left, right]while left right: # 区间不为空# 循环不变量# nums[left-1] target# nums[right1] targetmid (left right) // 2if nums[mid] target:left mid 1 # 范围缩小到 [mid1, right]else:right mid - 1 # 范围缩小到 [left, mid-1]return left # 或者 right1# 左闭右开区间写法 def lower_bound2(nums: List[int], target: int) - int:left, right 0, len(nums) # 左闭右开区间 [left, right)while left right: # 区间不为空# 循环不变量# nums[left-1] target# nums[right] targetmid (left right) // 2if nums[mid] target:left mid 1 # 范围缩小到 [mid1, right)else:right mid # 范围缩小到 [left, mid)return left # 或者 right# 开区间写法 def lower_bound3(nums: List[int], target: int) - int:left, right -1, len(nums) # 开区间 (left, right)while left 1 right: # 区间不为空mid (left right) // 2# 循环不变量# nums[left] target# nums[right] targetif nums[mid] target:left mid # 范围缩小到 (mid, right)else:right mid # 范围缩小到 (left, mid)return right # 或者 left1class Solution:def search(self, nums: List[int], target: int) - int:i lower_bound(nums, target) # 选择其中一种写法即可return i if i len(nums) and nums[i] target else -135. 搜索插入位置 题目描述给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 class Solution:def searchInsert(self, nums: List[int], target: int) - int:left, right 0, len(nums) - 1while left right:mid (left right) // 2if nums[mid] target:return midelif nums[mid] target:left mid 1else:right mid - 1return leftclass Solution:def searchInsert(self, nums: List[int], target: int) - int:left, right 0, len(nums) # 采用左闭右开区间[left,right)while left right: # 右开所以不能有,区间不存在mid left (right - left)//2 # 防止溢出, //表示整除if nums[mid] target: # 中点小于目标值,在右侧,可以得到相等位置left mid 1 # 左闭, 所以要1else:right mid # 右开, 真正右端点为mid-1return left # 此算法结束时保证left right, 返回谁都一样300. 最长上升子序列         题目描述给你一个整数数组 nums 找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

5. 动态规划 二分查找

   Dynamic programming Dichotomy.

   class Solution:def lengthOfLIS(self, nums: [int]) - int:tails, res [0] * len(nums), 0for num in nums:i, j 0, reswhile i j:m (i j) // 2if tails[m] num: i m 1 # 如果要求非严格递增将此行 改为 即可。else: j mtails[i] numif j res: res 1return res2. 动态规划 class Solution:def lengthOfLIS(self, nums: List[int]) - int:if not nums: return 0dp [1] * len(nums)for i in range(len(nums)):for j in range(i):if nums[j] nums[i]: # 如果要求非严格递增将此行 改为 即可。dp[i] max(dp[i], dp[j] 1)return max(dp)34. 在排序数组中查找元素的第一个和最后一个位置 题目描述给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target返回 [-1, -1]。 class Solution:def searchRange(self, nums: List[int], target: int) - List[int]:if not nums or target not in nums: # 特例二分查找失败return [-1, -1]return [self.lower_bound(nums, target), self.upper_bound(nums, target)]def upper_bound(self, nums: List[int], target: int): # 寻找上边界left, right 0, len(nums)-1while left right:mid left (right - left) // 2if nums[mid] target: # 移动左指针left mid 1else: # 移动右指针right mid -1return rightdef lowerbound(self, nums: List[int], target: int): # 寻找下边界left, right 0, len(nums)-1while left right:mid left (right - left) // 2if nums[mid] target: # 当nums[mid]大于等于目标值时继续在左区间检索找到第一个数right mid - 1else: # nums[mid]小于目标值时则在右区间继续检索找到第一个等于目标值的数left mid 1return left611. 有效三角形的个数         题目描述给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。 将数组 nums 进行升序排序随后使用二重循环枚举 a 和 b。设 anums[i],bnums[j]anums[i], bnums[j]anums[i],bnums[j]为了防止重复统计答案我们需要保证 ijijij。剩余的边 c 需要满足 cnums[i]nums[j]cnums[i]nums[j]cnums[i]nums[j]我们可以在 [j1,n−1][j1,n−1][j1,n−1] 的下标范围内使用二分查找其中 nnn 是数组 nums 的长度找出最大的满足 nums[k]nums[i]nums[j]nums[k]nums[i]nums[j]nums[k]nums[i]nums[j] 的下标 kkk这样一来在 [j1,k][j1, k][j1,k] 范围内的下标都可以作为边 ccc 的下标我们将该范围的长度 k−jk−jk−j 累加入答案。 1. 排序二分查找 class Solution:def triangleNumber(self, nums: List[int]) - int:nums.sort()length len(nums)ans 0for i in range(length):for j in range(i1, length):left, right j1, length while left right: # 找边界mid (left right)//2if nums[mid] nums[i] nums[j]:left mid 1else:right midans left - 1 - jreturn ans2. 排序双指针 我们将当 anums[i],bnums[j]anums[i], bnums[j]anums[i],bnums[j] 时最大的满足 nums[k]nums[i]nums[j]nums[k]nums[i]nums[j]nums[k]nums[i]nums[j] 的下标 kkk 记为 ki,jk{i,j}ki,j​。可以发现如果我们固定 iii那么随着 jjj 的递增不等式右侧 nums[i]nums[j]nums[i]nums[j]nums[i]nums[j] 也是递增的因此 ki,jk_{i,j}ki,j​ 也是递增的。 这样一来我们就可以将 jjj 和 kkk 看成两个同向递增移动的指针将方法一进行如下的优化 我们使用一重循环枚举 iii。当 iii 固定时我们使用双指针同时维护 jjj 和 kkk它们的初始值均为 iii我们每一次将 jjj 向右移动一个位置即 j←j1j←j1j←j1并尝试不断向右移动 kkk使得 kkk 是最大的满足 nums[k]nums[i]nums[j]nums[k]nums[i]nums[j]nums[k]nums[i]nums[j] 的下标。我们将 max(k−j,0)max(k−j, 0)max(k−j,0) 累加入答案。 class Solution:def triangleNumber(self, nums: List[int]) - int:nums.sort()length len(nums)ans 0for i in range(length):k i 1 for j in range(i1, length):while k1 length and nums[i] nums[j] nums[k1]:k 1ans max(k-j, 0)return ans436. 寻找右区间 题目描述 class Solution:def findRightInterval(self, intervals: List[List[int]]) - List[int]:start_map {interval[0] : i for i, interval in enumerate(intervals)} # 以区间左侧构建索引字典starts [interval[0] for interval in intervals] # 取出区间的左侧res []starts.sort()for interval in intervals:pos self.higher_find(starts, interval[1]) # 遍历每个区间的右侧在所有区间的左侧进行二分查找res.append(start_map[starts[pos]] if pos ! -1 else -1)return resdef higher_find(self, nums, target):left, right 0, len(nums) # 左闭右开while left right:mid left (right - left) // 2if nums[mid] target:right midelse:left mid 1if left len(nums) and nums[left] target: # 最后判断一下是否满足条件return leftreturn -14. 寻找两个正序数组的中位数 题目描述给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log(mn))O(log (mn))O(log(mn))。 class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:def getKthElement(k):- 主要思路要找到第 k (k1) 小的元素那么就取 pivot1 nums1[k/2-1] 和 pivot2 nums2[k/2-1] 进行比较- 这里的 / 表示整除- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个- 取 pivot min(pivot1, pivot2)两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) (k/2-1) k-2 个- 这样 pivot 本身最大也只能是第 k-1 小的元素- 如果 pivot pivot1那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 删除剩下的作为新的 nums1 数组- 如果 pivot pivot2那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 删除剩下的作为新的 nums2 数组- 由于我们 删除 了一些元素这些元素都比第 k 小的元素要小因此需要修改 k 的值减去删除的数的个数index1, index2 0, 0while True:# 特殊情况if index1 m:return nums2[index2 k - 1]if index2 n:return nums1[index1 k - 1]if k 1:return min(nums1[index1], nums2[index2])# 正常情况newIndex1 min(index1 k // 2 - 1, m - 1)newIndex2 min(index2 k // 2 - 1, n - 1)pivot1, pivot2 nums1[newIndex1], nums2[newIndex2]if pivot1 pivot2:k - newIndex1 - index1 1index1 newIndex1 1else:k - newIndex2 - index2 1index2 newIndex2 1m, n len(nums1), len(nums2)totalLength m nif totalLength % 2 1:return getKthElement((totalLength 1) // 2)else:return (getKthElement(totalLength // 2) getKthElement(totalLength // 2 1)) / 22.3 不完全有序 题库列表 题号链接33搜索旋转排序数组中等81搜索旋转排序数组 II中等153寻找旋转排序数组中的最小值中等154寻找旋转排序数组中的最小值 II困难852山脉数组的峰顶索引简单1095山脉数组中查找目标值中等

6. 搜索旋转排序数组 题目描述整数数组 nums 按升序排列数组中的值 互不相同。在传递给函数之前nums 在预先未知的某个下标 k(0knums.length)k(0 k nums.length)k(0knums.length) 上进行了旋转使数组变为 [nums[k],nums[k1],…,nums[n−1],nums[0],nums[1],…,nums[k−1]][nums[k], nums[k1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]][nums[k],nums[k1],…,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。 class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums)-1while left right:mid (left right) // 2if nums[mid] target:return midif nums[mid] nums[left]: # 左半部分有序if nums[0] target nums[mid]: # target 在左半部分right mid - 1else:left mid 1else: # 右半部分有序if nums[mid] target nums[len(nums)-1]: # target 在右半部分left mid 1else:right mid - 1return -181. 搜索旋转排序数组 II 题目描述 class Solution:def search(self, nums: List[int], target: int) - bool:left, right 0, len(nums)-1while left right:mid (left right)//2if nums[mid] target:return Trueif nums[mid] nums[left]: # 去重left 1continueif nums[left] nums[mid]: # 左半部分有序在左侧二分查找if nums[left] target nums[mid]:right mid - 1else:left mid 1else: # 右半部分有序在右侧二分查找if nums[mid] target nums[right]:left mid 1else:right mid - 1return False153. 寻找旋转排序数组中的最小值 题目描述 class Solution:def findMin(self, nums: List[int]) - int: low, high 0, len(nums) - 1while low high:pivot low (high - low) // 2if nums[pivot] nums[high]:high pivot else:low pivot 1return nums[low]154. 寻找旋转排序数组中的最小值 II 题目描述 class Solution:def findMin(self, nums: List[int]) - int:left, right 0, len(nums)-1while left right:mid (leftright) // 2if nums[mid] nums[right]:right midelif nums[mid] nums[right]:left mid 1else:right - 1 # 去重return nums[left]852. 山脉数组的峰顶索引简单 题目描述 1. 顺序查找 class Solution:def peakIndexInMountainArray(self, arr: List[int]) - int:# 顺序查找最大值for i in range(1, len(arr) - 1):if arr[i] arr[i 1]:return i2. 二分查找 class Solution:def peakIndexInMountainArray(self, arr: List[int]) - int:# 二分查找最大值left, right 0, len(arr) - 1while left right:mid (left right) // 2if arr[mid] arr[mid 1]:right midelse:left mid 1return left1095. 山脉数组中查找目标值 题目描述 class Solution:def findInMountainArray(self, target: int, mountain_arr: MountainArray) - int:先使用二分法找到数组的峰值。在峰值左边使用二分法寻找目标值。如果峰值左边没有目标值那么使用二分法在峰值右边寻找目标值。head, tail 0, mountain_arr.length()-1while head tail: # 找峰值注意越界处理mid (headtail)//2if mountain_arr.get(mid) mountain_arr.get(mid1):head mid 1else:tail midpeak headans self.binarySearch(mountain_arr, target, 0, peak) # 在左半边搜索if ans ! -1:return ansreturn self.binarySearch(mountain_arr, target, peak1, mountain_arr.length()-1, lambda x:-x) # 在右半边搜索def binarySearch(self, mountain, target, left, right, keylambda x: x): target key(target) # 这里的key相当于把两边全部转为升序部分也可以用target*reverse根据reverse的正负来判断while left right:mid (left right) // 2curr key(mountain.get(mid))if curr target:return midelif curr target:left mid 1else:right mid - 1return -12.4 二分答案在一个有范围的区间里搜索一个整数 如果题目要我们找一个整数这个整数有确定的范围可以通过二分查找逐渐缩小范围最后逼近到一个数。 定位一个有范围的整数这件事情也叫「二分答案」或者叫「二分结果」。如果题目要求的是一个整数这个整数有明确的范围可以考虑使用二分查找。 题号链接69x 的平方根简单287寻找重复数中等374猜数字大小简单

7. x 的平方根 题目描述给你一个非负整数 x 计算并返回 x 的算术平方根。由于返回类型是整数结果只保留整数部分 小数部分将被舍去 。 class Solution:def mySqrt(self, x: int) - int:left, right 0, x//2while left right:mid (left right) // 2if mid * mid x:return midif mid * mid x:left mid 1else:right mid - 1return left if left ** 2 x else left-1 287. 寻找重复数 题目描述给定一个包含 n1n1n1 个整数的数组 nums 其数字都在 [1,n][1, n][1,n] 范围内包括 1 和 n可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 返回 这个重复的数。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1)O(1)O(1) 的额外空间。

8. 二分法 设数组长度为nnn则数组中元素 ∈[1,n−1]\in[1, n-1]∈[1,n−1]且只有一个重复元素。一个直观的想法设一个数字 k∈[1,n−1]k\in[1,n-1]k∈[1,n−1]统计数组中小于等于 kkk 的数字的个数 count 若 countkcountkcountk说明重复数字一定在 (k,n−1](k,n−1](k,n−1] 的范围内。若 countkcountkcountk说明重复数字一定在 [0,k][0,k][0,k] 的范围内。 利用这个性质我们使用二分查找逐渐缩小重复数字所在的范围。 初试化左右 数字 边界 left1,rightn−1left1, rightn-1left1,rightn−1循环条件 leftright:leftright:leftright: mid(leftright)//2mid(leftright)//2mid(leftright)//2按照性质统计数组中小于等于 midmidmid 的元素个数 countcountcount若 countmidcountmidcountmid说明重复数字一定在 (mid,right](mid,right](mid,right] 的范围内。令 leftmid1leftmid1leftmid1若 countmidcountmidcountmid说明重复数字一定在 [left,mid][left,mid][left,mid] 的范围内。令 rightmidrightmidrightmid。 返回 leftleftleft class Solution:def findDuplicate(self, nums: List[int]) - int:left 1right len(nums) - 1while(leftright):mid(leftright)//2count0for num in nums:if(nummid):count1if(countmid):leftmid1else:rightmidreturn left2. 快慢指针 分为两步 找到环找到环的入口即重复元素 找环 定义快慢指针 slow0,fast0slow0, fast0slow0,fast0进入循环 - slowslowslow 每次走一步即 slownums[slow]slownums[slow]slownums[slow] - fastfastfast 每次走两步即 fastnums[nums[fast]]fastnums[nums[fast]]fastnums[nums[fast]] - 当 slowfastslowfastslowfast时退出循环。 当快慢指针相遇时一定在环内。此时假设slow 走了 kkk 步则 fast 走了 2k2k2k 步。设环的周长为 ccc则 kk%c0k。 找环的入口定义新的指针 find0find0find0进入循环 find 每次走一步即 findnums[find]findnums[find]findnums[find]slow每次走一步即 slownums[slow]slownums[slow]slownums[slow]当两指针相遇时即 findslowfindslowfindslow返回 find
   为何相遇时找到的就是入口 假设起点到环的入口(重复元素)需要 mmm 步。此时 slow 走了 nmnmnm 步其中 nnn 是环的周长 ccc 的整数倍所以相当于 slow走了 mmm 步到达入口再走了 nnn 步。所以相遇时一定是环的入口。 class Solution:def findDuplicate(self, nums: List[int]) - int:slow0fast0while(1):slownums[slow]fastnums[nums[fast]]if(slowfast):breakfind0while(1):findnums[find]slownums[slow]if(findslow):return find374. 猜数字大小 题目描述

   The guess API is already defined for you.

   param num, your guess

   return -1 if num is higher than the picked number

   1 if num is lower than the picked number

   otherwise return 0

   def guess(num: int) - int:class Solution:def guessNumber(self, n: int) - int:left, right 0, nwhile left right:mid left ((right-left)1)temp guess(mid)if temp 0:return midelif temp 1:left mid 1else:right mid -1小结 二分法暂时告一段落后面在学习中持续补充谢谢大家的鼓励和支持 参考

   二分查找算法https://ojeveryday.github.io/AlgoWiki/#/BinarySearch/README二分算法https://oi-wiki.org/basic/binary/二分查找https://www.cnblogs.com/jasonbourne3/p/17141780.html算法与数据结构七二分查找法总结https://blog.csdn.net/Dby_freedom/article/details/94332149一文带你搞定二分查找及其多个变种https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/写对二分查找不是套模板并往里面填空需要仔细分析题意https://leetcode.cn/problems/search-insert-position/solutions/10969/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/二分查找折半查找算法详解http://data.biancheng.net/view/336.html