【LeetCode 刷题】二分搜索

此博客作为《代码随想录》的学习笔记，主要内容为二分搜索法及相关题目解析。

文章目录

• 704. 二分查找
• 35.搜索插入位置
• 34.在排序数组中查找元素的第一个和最后一个位置
• 69.x 的平方根
• 367.有效的完全平方数

以下所有二分法算法均基于左闭右闭区间

704. 二分查找

LeetCode 题目链接

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

• while 循环的条件为 <=，不是 <
• right 更新为 mid - 1，不是 mid

35.搜索插入位置

LeetCode 题目链接

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

• 跳出 while 循环后，结果一定为 left 指针在 right 指针的右侧下一个的位置，即 left = right + 1
• 返回 left 或 right + 1 均可

34.在排序数组中查找元素的第一个和最后一个位置

LeetCode 题目链接

class Solution:
    def upperBound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (right - left) // 2 + left
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return left

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = self.upperBound(nums, target - 1)  # 左边界
        right = self.upperBound(nums, target) - 1  # 右边界
        
        if left <= right and right < len(nums) and nums[left] == target and nums[right] == target:
            return [left, right]
        return [-1, -1]

• upperBound 寻找上界，即第一个 > 目标值的位置
• 二分查找后返回元素的判断技巧：
  • 跳出 while 循环后，left = right + 1，也表明着两个指针现在互相进入了对方的区间，即左指针指向的元素满足的右区间的要求
  • 以上题为例， left 指针指向的元素满足右区间的判断条件，即 nums[left] > target；right 指针指向元素满足左区间的判断条件，即 nums[right] = nums[left-1] <= target
  • 因此返回 left，则找到了第一个 > 目标值的位置

69.x 的平方根

LeetCode 题目链接

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

• right 对应第一个满足 num * num <= x 的元素

367.有效的完全平方数

LeetCode 题目链接

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 0, num
        while left <= right:
            mid = (right - left) // 2 + left
            if mid * mid == num:
                return True
            elif mid * mid < num:
                left = mid + 1
            else:
                right = mid - 1
        return False

• 最基本的二分法