失眠网 > 200道大数据面试常考Leetcode算法题--二分查找篇（python带代码解析）

200道大数据面试常考Leetcode算法题--二分查找篇（python带代码解析）

时间：2021-09-25 09:14:44

往期内容在这里：

往期01-05

往期06-10

往期11-15

往期16-20

数组篇01

数组篇02

数组篇03

数组篇04

动态规划篇

动态规划进阶(与矩阵相关)

动态规划再进阶(序列类动态规划问题)

大家好，继续为大家推荐200道大数据面试常考Leetcode算法题，这期为--二分查找篇，附带解析，都是从Leetcode官网总结大神们的解法（在这里感谢大神的帮助，我只是个搬运工！）这篇更新6篇，艾瑞巴迪和我一起刷起来！！

200道大数据面试常考Leetcode算法题（二分查找篇）34-在排序数组中查找元素的第一个和最后一个位置
Leetcode原题为：
题解为：
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道大数据面试常考Leetcode算法题（二分查找篇）69-x 的平方根
Leetcode原题为：
题解为：
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道大数据面试常考Leetcode算法题（二分查找篇）74-搜索二维矩阵
Leetcode原题为：
题解为：
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道大数据面试常考Leetcode算法题（二分查找篇）153-寻找旋转排序数组中的最小值
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道大数据面试常考Leetcode算法题（二分查找篇）278-第一个错误的版本
Leetcode原题为：
题解为:
class Solution:def firstBadVersion(self, n):# 定义左右边界，因为是版本是一个个体，所以从1开始l,r = 1,n# 当左边界小于右边界循环while (l<r):# 找到中间索引mid = (l+r)//2# 判断中值是否为错误版本，假如是，# 即表示第一个错误版本在左边，重新开始让区间右边界变为从中值开始if isBadVersion(mid):r = mid# 否则表示第一个错误版本在右边，重新开始让区间左边界变为从中值+1开始else:l = mid+1# 当左右边界相等时即找到第一个错误版本return l

200道大数据面试常考Leetcode算法题（二分查找篇）540-有序数组中的单一元素
Leetcode原题为：
题解为：
class Solution:def singleNonDuplicate(self, nums: List[int]) -> int:l,r = 0,len(nums)-1while(l < r):mid = (l+r) // 2# 右侧数组为偶数halvesAreEven = (l - mid) % 2 == 0# 假如中值和中值后面的数是一对时if(nums[mid] == nums[mid + 1]):# 否则右侧数组为偶数，说明单一数字在右侧，重新开始让区间左边界变为从中值+2开始# 因为中值右侧有一个跟中间相同，所以不能右侧此时不能是偶数if(halvesAreEven):l = mid + 2# 否则左侧数组为偶数，说明单一数字在右侧，重新开始让区间左边界变为从中值+2开始else:r = mid - 1# 假如中值和中值前面的数是一对时elif(nums[mid] == nums[mid - 1]):# 假如右侧数组为偶数，说明单一数字在左侧，重新开始让区间右边界变为从中值-2开始if(halvesAreEven):r = mid -2# 否则左侧数组为偶数，说明单一数字在右侧，重新开始让区间左边界变为从中值+1开始else:l = mid + 1# 否则中值就是单一数字else:return nums[mid]# 当左右边界相同时，即找到单一数字return nums[l]