初学python的我开始Leetcode题10-3

发布于：2025-06-26 ⋅ 阅读:(17) ⋅ 点赞:(0)

提示：100道LeetCode热题-10-3主要是二分查找相关，包括三题：搜索插入位置、搜索二维矩阵、在排序数组中查找元素的第一个和最后一个位置。由于初学，所以我的代码部分仅供参考。

前言

才发现原题粘过来黑黑的，改了一下~

最近在学知识图谱，但还是不班门弄斧啦~Leetcode启动！

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。事实上，在一些理论课上我们早就学会过它，它通过反复将数组分成两半来缩小搜索范围，从而快速找到目标元素。那么怎么运用呢？以下是二分查找的基本步骤：

  1. 确定数组的中间元素。

  2. 将目标值与中间元素进行比较。

  3. 如果目标值等于中间元素，则查找成功。

  4. 如果目标值小于中间元素，则在数组的左半部分继续查找。

  5. 如果目标值大于中间元素，则在数组的右半部分继续查找。

  6. 重复上述步骤，直到找到目标值或搜索范围为空。

二分查找的时间复杂度为 O(logn)，其中 n 是数组的长度。这使得二分查找在处理大型数据集时非常高效。

提示：以下是本篇文章正文内容，下面结果代码仅供参考

题目1：搜索插入位置

1.题目要求：

题目如下：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

  • 1 <= nums.length <= 10^{4}
  • -10^{4} <= nums[i] <= 10^{4}
  • nums 为 无重复元素 的 升序 排列数组
  • -10^{4} <= target <= 10^{4}

代码框架已经提供如下：

class Solution(object):

    def searchInsert(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: int

        """

2.结果代码：

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

说明：

  • 初始化两个指针 left 和 right，分别指向数组的起始和结束位置。

  • 进入循环，当 left 小于等于 right 时：

    • 计算中间索引 mid。

    • 如果 nums[mid] 等于目标值 target，直接返回 mid。

    • 如果 nums[mid] 小于目标值 target，说明目标值在数组的右侧，将 left 移动到 mid + 1。

    • 如果 nums[mid] 大于目标值 target，说明目标值在数组的左侧，将 right 移动到 mid - 1。

  • 如果循环结束后仍未找到目标值，此时 left 指针指向的位置即为目标值应该插入的位置，直接返回 left。

题目2：搜索二维矩阵

1.题目要求：

题目如下：

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -10^{4} <= matrix[i][j], target <= 10^{4}

代码框架已经提供如下：

class Solution(object):

    def searchMatrix(self, matrix, target):

        """

        :type matrix: List[List[int]]

        :type target: int

        :rtype: bool

        """

2.结果代码：

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False
        left, right = 0, len(matrix) * len(matrix[0]) - 1
        while left <= right:
            mid = (left + right) // 2
            mid_value = matrix[mid // len(matrix[0])][mid % len(matrix[0])]
            if mid_value == target:
                return True
            elif mid_value < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

说明：

  • 首先判断矩阵是否为空，如果为空则直接返回 False。

  • 初始化两个指针 left 和 right，分别指向矩阵的起始和结束位置。

  • 进入循环，当 left 小于等于 right 时：

    • 计算中间索引 mid。

    • 根据 mid 计算出对应的矩阵中的行索引和列索引，得到中间值 mid_value。

    • 如果 mid_value 等于目标值 target，直接返回 True。

    • 如果 mid_value 小于目标值 target，说明目标值在矩阵的右侧，将 left 移动到 mid + 1。

    • 如果 mid_value 大于目标值 target，说明目标值在矩阵的左侧，将 right 移动到 mid - 1。

  • 如果循环结束后仍未找到目标值，返回 False。

题目3：在排序数组中查找元素的第一个和最后一个位置

1.题目要求：

题目如下：

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [
5,7,7,8,8,10]
, target = 8
输出：[3,4]

示例 2：

输入：nums = [

5,7,7,8,8,10]

, target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 10^{5}

  • -10^{9} <= nums[i] <= 10^{9}

  • nums 是一个非递减数组

  • -10^{9} <= target <= 10^{9}

代码框架已经提供如下：

class Solution(object):

    def searchRange(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: List[int]

        """

2.结果代码：

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        def binary_search_left(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left

        def binary_search_right(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1
            return right

        left = binary_search_left(nums, target)
        if left == len(nums) or nums[left] != target:
            return [-1, -1]
        right = binary_search_right(nums, target)
        return [left, right]

说明：

  • 定义了两个辅助函数 binary_search_left 和 binary_search_right，分别用于查找目标值的左边界和右边界。

  • 在 binary_search_left 中，当 nums[mid] < target 时，将 left 移动到 mid + 1；否则，将 right 移动到 mid - 1。最终返回 left，即目标值的左边界。

  • 在 binary_search_right 中，当 nums[mid] <= target 时，将 left 移动到 mid + 1；否则，将 right 移动到 mid - 1。最终返回 right，即目标值的右边界。

  • 调用 binary_search_left 查找目标值的左边界，如果目标值不存在于数组中，则返回 [-1, -1]。

  • 如果目标值存在于数组中，调用 binary_search_right 查找目标值的右边界，并返回 [left, right]。

总结

注意以上代码还有优化空间，大家可以自己动手尝试更优算法！

针对二分查找的三种题型进行了学习，了解了部分有关二分查找与python的相关知识，大家加油！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布