Leetcode 二分法

奋斗吧
奋斗吧
擅长邻域：未填写

标签： Leetcode 二分法 Python博客 51CTO博客

2023-05-15 18:24:06 226浏览

Leetcode 二分法，二分法475.供暖器方法一：二分查找方法二：滑动窗口[374.猜数字大小](https://leetcode-cn.com/problems/guess-number-higher-or-lower/)[35.搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/)方法一：方法二：二分[69.Sqrt(x)](ht



二分法

  • 475. 供暖器
  • 方法一：二分查找
  • 方法二：滑动窗口
  • [374. 猜数字大小](https://leetcode-cn.com/problems/guess-number-higher-or-lower/)
  • [35. 搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/)
  • 方法一：
  • 方法二：二分
  • [69. Sqrt(x)](https://leetcode-cn.com/problems/sqrtx/)
  • 方法一：袖珍计算器算法
  • 方法二：二分查找
  • 方法三：牛顿迭代
  • 方法四：位运算
  • [240. 搜索二维矩阵 II](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/)
  • 方法一：直接查找
  • 方法二：二分查找
  • 方法三：Z 字形查找
  • [852. 山脉数组的峰顶索引](https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/)
  • [278. 第一个错误的版本](https://leetcode-cn.com/problems/first-bad-version/)
  • [367. 有效的完全平方数](https://leetcode-cn.com/problems/valid-perfect-square/)


475. 供暖器

Leetcode 在加热站中找到每个房屋需要的最小半径的最大值

方法一：二分查找

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        
        heaters.sort()
        # heaters.insert(0, -inf) # 添加哨兵
        # heaters.append(inf)
        # res = 0
        # for h in houses:
        #     # 二分法找 h 右边最近加热器, 减一为左边
        #     idx = bisect.bisect(heaters, h)
        #     res = max(res, min(h - heaters[idx - 1], heaters[idx] - h))
  
        res, n = 0, len(heaters)
        for h in houses:            
            left, right = 0, n;
            while left < right:
                mid = left + (right - left) // 2
                if h > heaters[mid]: left = mid + 1
                else: right = mid
            
            dist1 = inf if right == 0 else h - heaters[right - 1] 
            dist2 = inf if right == n else heaters[right] - h
            res = max(res, min(dist1, dist2))
        
        return res

方法二：滑动窗口

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
       
        houses.sort()
        heaters.sort()
        heaters.insert(0, -inf) # 添加哨兵
        heaters.append(inf)

        i, ans = 0, 0
        for h in houses:            
            while heaters[i] <= h:  # 找 h 右边第一个热站（刚好 > h）， i - 1 是左边的第一个或正好是 h                
                i += 1
            ans = max(ans, min(h - heaters[i-1], heaters[i] - h))
            # h 后面的不可能使用，i - 1 前面的热站，所以从 i 继续循环。 [heaters[i-1], heaters[i]] 滑动窗口 
        return ans

374. 猜数字大小 

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   # 答案在区间 [left, mid] 中
            else:
                left = mid + 1   # 答案在区间 [mid+1, right] 中
        
        # 此时有 left == right，区间缩为一个点，即为答案
        return left

35. 搜索插入位置

方法一：

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if target > nums[-1]: return n # 最后
        if target < nums[0]: return 0 # 开头
        
        for i in range(n):
            if nums[i] == target: return i # 相等
            if nums[i] > target: return i  # 刚好大于位置

方法二：二分

在数组中插入目标值，四种情况：

Leetcode 二分法_算法


在二分查找的过程中，保持不变量——循环不变量。

闭区间 Leetcode 二分法_List_02

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:        
        n = len(nums)
        l, r = 0, n - 1 # 定义 target 在闭区间 [left, right]
        while l <= r: # 当 left == right，区间 [left, right] 依然有效
            mid = (l + r) // 2
            if nums[mid] == target: return mid
            if nums[mid] < target:  l = mid + 1 # target 在右区间 [middle+1, right]
            else: r = mid - 1 # target 在左区间 [left, middle-1]
            
        return l # or r + 1 左边 l 或右边 r + 1

        #return bisect.bisect_left(nums, target)

半开半闭区间 Leetcode 二分法_二分查找_03

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:        
        n = len(nums)
        l, r = 0, n # 定义 target 在半闭半开区间 [left, right)
        while l < r: # 因为 left == right 的时候，[left, right)是空区间
            mid = (l + r) >> 1
            if nums[mid] == target: return mid
            if nums[mid] < target:  l = mid + 1 # target 在右区间 [middle+1, right) 
            else: r = mid # target 在左区间 [left, middle) 注意没有 - 1
            
        return r # or l

69. Sqrt(x)

方法一：袖珍计算器算法

「袖珍计算器算法」是一种用指数函数 exp 和对数函数 ln 代替平方根函数的方法。

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        ans = int(math.exp(0.5 * math.log(x)))
        return ans + 1 if (ans + 1) ** 2 <= x else ans

方法二：二分查找

由于 x 平方根的整数部分 ans 是满足 Leetcode 二分法_二分查找_04 ≤ x 的最大 k 值，因此可以对 k 进行二分查找，从而得到答案。
二分查找的下界为 0，上界可以粗略地设定为 x。

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r, ans = 0, x, -1
        while l <= r:
            mid = (l + r) // 2
            if mid * mid <= x:
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans

方法三：牛顿迭代

牛顿迭代法是一种可以用来快速求解函数零点的方法。

Leetcode 二分法_python_05

Leetcode 二分法_python_06

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0: return 0
        
        C, x0 = x, x
        while True:
            xi = 0.5 * (x0 + C / x0)
            if abs(x0 - xi) < 1e-7:
                break
            x0 = xi
        
        return int(x0)

方法四：位运算

class Solution:
    def mySqrt(self, x: int) -> int:
        res = x
        while res*res > x:
            res = (res + x//res) >> 1

        return res

240. 搜索二维矩阵 II

方法一：直接查找

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            for element in row:
                if element == target: return True
                
        return False

方法二：二分查找

for row in matrix:
            # if row[-1] < target: continue
            # if row[0] > target:  break
            # idx = bisect.bisect_left(row, target)
            # if idx < len(row) and row[idx] == target:
            #     return True

            if target in row: return True
        
        # return False

方法三：Z 字形查找

i, j = 0, len(matrix[0]) - 1
        while i < len(matrix) and j >= 0:
            if matrix[i][j] == target: return True
            if matrix[i][j] > target: j -= 1
            else: i += 1

        # return False

852. 山脉数组的峰顶索引 

```python3
class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        # 方法一：
        '''     
        for i in range(1, len(arr)-1):
            if arr[i] > arr[i+1]:
                return i
        
        # 方法二：二分
        i, j = 0, len(arr) - 1
        while i < j:
            mid = (i+j)//2
            if arr[mid+1] > arr[mid]:
                i = mid + 1
            else:
                j = mid 
               
        return j 
        '''
        return arr.index(max(arr))

278. 第一个错误的版本 

class Solution:
    def firstBadVersion(self, n):
        # i, j = 1, n
        # while i <= j:
        #     mid = (i + j) // 2
        #     if isBadVersion(mid):
        #         j = mid - 1
        #     else:
        #         i = mid + 1            
      
        # return j + 1

        l, r = 1, n        
        while l < r:
            m = l + ((r - l) >> 1)
            if isBadVersion(m):
                r = m
            else:
                l = m + 1
        
        return l

367. 有效的完全平方数 

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num == 1: return True
        # 方法一：二分查找
        '''
        i, j = 2, num // 2
        while i <= j:
            m = (i + j) // 2
            if num == m ** 2:
                return True
            if num > m ** 2:
                i = m + 1
            else:
                j = m - 1

        return False
        '''

        # 方法二：牛顿迭代法
        x = num // 2
        while x * x > num:
            x = (x + num // x) // 2
            
        return x * x == num

其他「二分」相关题解
二分模板
29. 两数相除 : 二分 + 倍增乘法解法（含模板）

二分模板题
278. 第一个错误的版本 : 使用交互函数充当 check 进行二分

  1. 猜数字大小 : 使用交互函数充当 check 进行二分
  2. 山脉数组的峰顶索引 : 二分 & 三分查值问题

二分本质 & 恢复二段性处理
33. 搜索旋转排序数组（找目标值） : 严格 O(logN)，一起看清二分的本质

  1. 搜索旋转排序数组 II（找目标值） : 详解为何元素相同会导致 O(n)，一起看清二分的本质
  2. 寻找旋转排序数组中的最小值（找最小值） : 严格 O(logN)，一起看清二分的本质
  3. 寻找旋转排序数组中的最小值 II（找最小值） : 详解为何元素相同会导致 O(n)，一起看清二分的本质

二分 check 函数如何确定
34. 在排序数组中查找元素的第一个和最后一个位置 : 考察对「二分」的理解，以及 check 函数的「大于 小于」怎么写


好博客就要一起分享哦！分享海报

此处可发布评论

评论（0）展开评论

暂无评论，快来写一下吧

展开评论

您可能感兴趣的博客

客服QQ 1913284695