200道大数据面试常考Leetcode算法题 _动态规划

往期内容在这里：
往期01-05
往期06-10
往期11-15
往期16-20
数组篇01
数组篇02
数组篇03
数组篇04
动态规划篇
动态规划进阶(与矩阵相关)
动态规划再进阶(序列类动态规划问题)
大家好，继续为大家推荐200道大数据面试常考算法题，这期为--二分查找篇，附带解析，都是从官网总结大神们的解法（在这里感谢大神的帮助，我只是个搬运工！）这篇更新6篇，艾瑞巴迪和我一起刷起来！！200道大数据面试常考算法题（二分查找篇）34-在排序数组中查找元素的第一个和最后一个位置
原题为：
题解为：
class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:# 左右端点l, r = 0, len(nums)-1# 从左往右循环while l <= r:# 找到中间值的索引mid = (l+r)//2# 假如中间值就算目标值if nums[mid] == target:# 找到中间值左边开始索引跟右边开始索引if nums[l] == target and nums[r] == target:return [l,r]# 没找到左边右移一位if nums[l] != target:l += 1# 没找到右边左移一位if nums[r] != target:r -= 1# 假如目标值大于中间值，则l,r 都在mid右边elif nums[mid] < target:# 则重新定义左边从中间值开始变大l = mid + 1# 假如目标值小于中间值，则l,r 都在mid左边else: # 则重新定义右边值从中间值开始变小r = mid - 1# 没有即返回-1，-1return [-1,-1]
200道大数据面试常考算法题（二分查找篇）69-x 的平方根
原题为：
题解为：
class Solution(object):def mySqrt(self, x):# 左边界，因数low, high = 0, x# 当左边界小于等于因数，开始循环while (low <= high):# 找到中值mid = (low + high) // 2# 假如因数平方大于目标值，说明最终符合因数在当前中值的左边边，那么因数减一if mid * mid > x:high = mid - 1# 否则最终符合因数在当前中值的右边else:low = mid + 1# 退出循环，输出当前的因数return int(high)
200道大数据面试常考算法题（二分查找篇）74-搜索二维矩阵
原题为：
题解为：
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:# 对列表的每个列表开始循环for list in matrix:# 左右边界l, r = 0, len(list)-1# 左边界小于等于有边界while l <= r:# 找到中值mid = (l+r)//2# 假如当前列表的中值为目标值，是即返回Trueif list[mid] == target:return True# 假如当前列表的中值小于目标值，说明目标值在中值的右边，左边界变为中值开始加一elif list[mid] < target:l = mid+1# 假如当前列表的中值大于目标值，说明目标值在中值的左边，右边界变为中值开始减一else:r = mid-1# 假如找不到目标值即返回Falsereturn False
200道大数据面试常考算法题（二分查找篇）153-寻找旋转排序数组中的最小值

文章插图
【200道大数据面试常考Leetcode算法题】原题：
题解为：

class Solution:def findMin(self, nums: List[int]) -> int:# 左右边界l,r = 0,len(nums)-1# 左边界小于右边界开始循环while(l < r):# 计算中值索引mid = (l + r) // 2# 假如中值大于右边界，说明最小值在右边界，重新开始让区间左边界变为从中值+1if(nums[mid] > nums[r]):l = mid+1# 假如中值小于等于右边界，说明最小值在左边界，重新开始让区间右边界变为从中值开始else:r = mid# 最后当左右边界相同的时侯，即找到最小值return nums[l]

200道大数据面试常考算法题（二分查找篇）278-第一个错误的版本