leetcode 二分查找小结

这篇具有很好参考价值的文章主要介绍了leetcode 二分查找小结。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

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

leetcode 二分查找小结
原始思路:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
    	# 1. 一般情况:利用二分查找不断缩小区间,直到找到target所在的位置,然后通过左右移动确定最终target所在的区间。
		# 2. 考虑list为空的情况。
		# 3. 考虑low high本身就等于target的情况。
        n = len(nums)
        if n == 0:
            return [-1, -1]

        low = 0
        high = n - 1
        while(high - low > 1):
            mid = (low + high) // 2
            if nums[mid] > target:
                high = mid - 1
            else:
                low = mid
        if nums[high] == target:
            low = high
        
        if n == 0 or nums[low] != target:
            return [-1, -1]
        else:
            # 以最终的mid为起点,往两边挪一挪
            while(low - 1 >= 0 and nums[low - 1] == nums[low]):
                low -= 1

            high = low
            while(high + 1 <= n-1 and nums[high + 1] == nums[low]):
                high += 1
            
            return [low, high]

但是,挪一挪的步骤最差的时候时间复杂度也能达到O(n),所以另一种避免这种情况的思路是我们分别使用二分查找去寻找区间的最左和最右。
上面的寻找target的代码(while …)无法精确地找到最左,因此我们需要对其进行一些改写。关键是要在找到一个值的时候不跳出循环,而是继续往左或者往右二分查找当前值。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:

        n = len(nums)

        low, high = 0, n - 1
        left, right = 0, 0

        # 寻找最左
        while(low <= high):
            mid = (low + high) // 2
            if nums[mid] > target:
                high = mid - 1  
            elif nums[mid] < target:
                low = mid + 1
            else:
                left = mid
                high = mid - 1 # 加上等于target的条件,可以在找到的时候继续往左边找
        
        # 没找到的情况
        if len(nums) == 0 or nums[left] != target:
            return [-1, -1]

        high = n - 1
        # 寻找最右
        while(low <= high):
            mid = (low + high) // 2
            print(mid, nums[mid], target)
            if nums[mid] > target:
                high = mid - 1  
            elif nums[mid] < target:
                low = mid + 1
            else:
                right = mid
                low = mid + 1 # 加上等于target的条件,可以在找到的时候继续往左边找

        return [left, right]

240. 搜索二维矩阵

这个矩阵可以视为左上角为root的二叉搜索树。(也可以右下角为root,改一下变大变小的规则就行)
leetcode 二分查找小结

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 初始位置:(i, j)
        # 如果target比cur_val (i,j)大,则变成(i+1, j)
        # 如果target比cur_val (i,j)小,则变成(i, j-1)
        
        m = len(matrix)
        n = len(matrix[0])

        i = 0
        j = n - 1
        while(i < m and j >= 0):
            cur_val = matrix[i][j]
            print(i, j, cur_val, target)
            if cur_val == target:
                return True
            elif cur_val > target:
                j -= 1
            else:
                i += 1

        return False

378. 有序矩阵中第 K 小的元素

leetcode 二分查找小结
与上一题类似,利用矩阵两个方向递增的性质。

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        # 1 5 9
        # 10 [11] 13
        # *12 13 13

        # 同样的,把这个矩阵视作一个二叉搜索树
        # 判断矩阵中小于等于mid的值是否有k个
        # 如果有的话,就往左半部分继续找
        # 如果没有,就往右半部分继续找

        def cal(matrix, mid, n):
            # O(n) 计算小于等于mid的值的个数
            i = n - 1
            j = 0

            num = 0
            while(i >= 0 and j < n):
                if matrix[i][j] <= mid:
                    num += i + 1        # 这种情况所在的一列都可以不看了
                    j += 1              # 往右边大的方向走
                else:
                    i -= 1              # 往上面往小的方向走
            
            return num 
 
        
        n = len(matrix)
        left = matrix[0][0]
        right = matrix[n-1][n-1]

        while(left < right):
            mid = left + (right - left) // 2   
            left_num = cal(matrix, mid, n)

            # 这种写法是错误的,因为有可能mid不在矩阵中
            # if left_num > k:
            #     right = mid - 1
            # elif left_num == k:
            #     return mid
            # else:
            #     left = mid + 1

            if left_num >= k:
                # 可能等于mid也可能不等于
                right = mid
            else:
                # 肯定需要继续往右找
                left = mid + 1

        # 返回left或者right都是一样的
        return left

        
             

287. 寻找重复数

leetcode 二分查找小结
只有一个数字会重复,但是一个数字可能会重复多次。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 如果不考虑空间复杂度 O(n)的时间复杂度
        # times_dict = {}
        # for n in nums:
        #     if n not in times_dict.keys():
        #         times_dict[n] = 1
        #     else:
        #         return n

        
        # 运用二分法实现O(1)复杂度的方法
        # 对于数字i,如果小于i的数字没有i-1个,则说明其重复了
        low = 1
        high = n
        while(low < high):
            mid = low + (high - low) // 2

            counter = 0
            for n in nums:
                if n <= mid:
                    counter += 1
            if counter > mid:
                # 继续往mid左边找,包括mid
                # 像这种low或者high可能等于mid的,就用while(low < high)否则可能跳不出循环
                high = mid
            elif counter <= mid:
                # 正常,往右边找,不包括mid
                low = mid + 1
		
		# 返回low和high都是一样的
        return low

33. 搜索旋转排序数组

leetcode 二分查找小结
这一题主要需要理解当你设置一个中间值的时候,左半部分或者右半部分总有一个是有序的。确认了哪部分是有序的之后,我们就更方便确定区间是在左边还是在右边了。
leetcode 二分查找小结文章来源地址https://www.toymoban.com/news/detail-476210.html

class Solution:
    def search(self, nums: List[int], target: int) -> int:

        n = len(nums)
        low = 0
        high = n - 1

        # 旋转后的数组是局部有序的,且无论如何,左右总会有一半是有序的
        while(low <= high):         # 加上等于号防止与return -1的情况混淆
            mid = low + (high - low) // 2
            if nums[mid] == target:
                return mid

            # 如果左边是有序的,那肯定是从小到大
            if nums[0] <= nums[mid]:
                if nums[low] <= target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            # 如果右边是有序的,肯定也是从小到大
            else:
                if nums[mid] < target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1

        return -1

总结

  1. 二分查找适合有序或部分有序的数组或者矩阵。
  2. 需要注意的点:
    a. 二分查找结束点的确定:如果中间high或者low可能等于mid,那么就用low < high作为循环结束条件;否则用low <= high作为循环结束条件,因为反正不会相等。
    b. 二分查找左右区间的赋值:看需求,主要需要判断以下什么情况更新low/high为mid / mid+1 / mid-1。
    c. 二分查找最后返回值的确定:因为最后跳出来的时候一般high=low,所以返回最终的high或者low即可。

到了这里,关于leetcode 二分查找小结的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录 LeetCode数组篇 二分查找

    # (简单)704. 二分查找 题目链接 代码随想录 - 二分查找思路 二分查找,思路很简单,但是在while循环left和right的比较是写=还是,还有right=mid还是right=mid-1容易混淆 需要想清楚对区间的定义,是[left,right],还是[left,right) (版本一,左闭右闭版本) (版本二,左闭右开) 题目

    2024年02月02日
    浏览(50)
  • LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】

    给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。 示例 1: 输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]],

    2024年04月14日
    浏览(42)
  • 34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)

    二分查找到目标值然后左右找到坐标 问题在于:找左右坐标的时候时间复杂度不是 O(logN) 之前提到过二分查找不仅可找到相等的数值,更关键的是 它可以将数组分为截然不同的两种情况 ,因此我们可以借助这个性质找到 第一个大于等于 target 的值(左下标) 和 第一个大于

    2024年01月22日
    浏览(50)
  • 二分查找:34. 在排序数组中查找元素的第一个和最后一个位置

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》《C++》《算法》 本篇文章仅是作为小白的我的一些理解,,如果有错误的地方,希望大佬们指出。 题目链接: 34. 在排序数组中查找元素的第一个和最后一个位置 本题数组元素不唯一,可能存在多个target,我们就是

    2024年02月08日
    浏览(47)
  • 二分查找实例1(在排序数组中查找元素的第一个和最后一个位置)

    给你一个按照非递减顺序排列的整数数组  nums ,和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ,返回  [-1, -1] 。 你必须设计并实现时间复杂度为  O(log n)  的算法解决此问题。 示例 1: 示例 2: 示例 3: 提示

    2024年02月09日
    浏览(44)
  • [二分查找]LeetCode2040:两个有序数组的第 K 小乘积

    二分查找算法合集 给你两个 从小到大排好序 且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k ,请你返回第 k (从 1 开始编号)小的 nums1[i] * nums2[j] 的乘积,其中 0 = i nums1.length 且 0 = j nums2.length 。 示例 1: 输入:nums1 = [2,5], nums2 = [3,4], k = 2 输出:8 解释:第 2 小的乘

    2024年02月04日
    浏览(37)
  • 【Leetcode每日一题】35.搜素插入位置|二分查找数组下标

    🌱博主简介:大一计科生,努力学习Java中!热爱写博客~预备程序媛 📜所属专栏:LeetCode每日一题–进击大厂 ✈往期博文回顾: 【JavaSE】保姆级教程|1万字+10张图学会类与对象–建议收藏 🕵️‍♂️近期目标:成为千粉小博主。 🌺“再牛的程序员也是从小白开始,既然开始

    2024年02月21日
    浏览(58)
  • 【算法|二分查找No.4】leetcode 852. 山脉数组的峰顶索引

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月05日
    浏览(62)
  • leetcode分类刷题:二分查找(Binary Search)(四、基于值域的数组/矩阵类型)

    基于值域的二分法与基于定义域的题型不同,它的目标是从一“ 特殊排序序列 ”中确定“第k个元素值”,而不像基于定义域的题型是从排序序列中找小于等于特定target值的第一个索引;同时,针对“特殊排序序列”,往往需要 嵌套使用双指针 法进行操作,进一步增加了对

    2024年02月11日
    浏览(58)
  • 快排&超详细,Leetcode排序数组题目带你升华掌握

    大家好,这里是Dark FalmeMater。 这篇文章我将超级仔细地讲解快速排序,快排之所以叫快排,到底有多快,为什么这么快,还有快速排序的优化和改进,通过这篇文章你一定会对快排有进一步的掌握。 快排的历史及介绍 快速排序由C. A. R. Hoare在1962年提出。 它的基本思想是:通

    2024年02月08日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包