专栏首页用户6811391的专栏吃透二分查找—— LeetCode 第 33、34、35 题记

吃透二分查找—— LeetCode 第 33、34、35 题记

昨天没能完成 34,今天来补上。恰好第 35 题也是二分查找算法的应用,放到一起来记录。

首先看下二分查找算法的概念:

❝二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。百度百科:二分查找 ❞

使用的题目中,一般会提到要求时间复杂度为 O(log n) 级别,以及涉及到的列表、数组是有序排列的。结合今天要记的三道题,我们来练习下这种解法的应用。在难度上,第 35 题简单,33、34 是中等难度,我们先看简单的。

题目一

「第 35 题:搜索插入位置」

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

你可以假设数组中无重复元素。

示例 1: 
输入: [1,3,5,6], 5
输出: 2

示例 2:
输入: [1,3,5,6], 2
输出: 1

示例 3:
输入: [1,3,5,6], 7
输出: 4

示例 4:
输入: [1,3,5,6], 0
输出: 0
#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/search-insert-position

题目分析

要在排序数组中找目标值的位置,很典型的二分查找的应用场景。当目标不存在时,返回目标应该被插入的位置。这个我们先把特殊情况择出来:列表长度不到 2 的情况,目标值大小超出列表值范围情况。正常二分查找的操作类似双指针法,定义一前一后两个索引,每次取其中间位置的值来进行判断,直到最终定位出结果。

比如示例 1,我们分别先取第一位 1 和最后一位 6 作为前后位置,此时中间位置为第 2 位 3,3 小于目标值,所以我们把范围缩小到右半部;缩小范围后,第 2 位 3 成了左侧边界,最后一位 6 仍是右边界,此时中间位置为 第 3 位 恰好为 5 目标值,所以返回第 3 位的坐标 2,任务完成。

这题要注意的点是,若存在目标值,返回其坐标;若不存在,要返回目标应该插入的位置。

代码实现

看二分法,通常都会纠结于比较完中点值后,对之后左右边界如何划分,究竟取 mid、mid-1 还是 mid+1 作为新的坐标,这个要具体来分析。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
    	# 空列表情况
        if nums==[]:
            return 0
        length = len(nums)
        # 只有一个数的列表情况
        if length<2:
            if nums[0]>=target:
                return 0
            else:
                return 1
        # 目标值不在列表值范围内情况
        if target<=nums[0]:
            return 0
        if target> nums[-1]:
            return length
        
        # 二分查找法开始
        # 定义左右边界位置,最左端和最右端索引
        l,r = 0,length-1
        # while 循环控制 l 和 r 来缩小范围
        while l<r:
        	# 取中点,这里的取值会偏左,比如第 1、2 位取的中点是第 1 位
            mid = (l+r)//2
            # 如果中点处值为目标,直接返回中点索引
            if nums[mid]==target:
                return mid
            # 若中点值大于目标,目标在左边部分,此时将右边界变为 mid
            # 这里不取 mid-1 的原因:取中点是偏左的,是无法取到右边界处的;如果 mid-1 处恰好为目标值,将其定为右边界就会导致中点无法取到该位置,故右边界我们取 mid
            elif nums[mid]>target:
                r = mid
            # 左边界可以跳过 mid 取 mid+1 原因在于,取中点可以取到左边界
            else:
                l = mid+1
        # 无论是否存在目标,经历过循环后,l 为目标的位置索引
        return l

提交代码测试:

执行用时 : 40 ms, 在所有 Python3 提交中击败了 79.75% 的用户
内存消耗 : 14.4 MB, 在所有 Python3 提交中击败了 7.14% 的用户

当然也有其它取巧的方法,我们先忽略,主要练习这个二分查找,继续看下一道

题目二

「第 33 题:搜索旋转排序数组」

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

题目分析

如果暴力遍历的话,时间复杂度是 O(n) 级别,因为需要对 n 个元素一一处理。若使用二分查找,时间复杂度就变为 log2 n 了,因为每次都是对半,比如有 8 个数、我们 3 次对半分便能完成定位。

此题目中提到原本排好序的列表,被调整了一次。看似不太符合二分查找时对排序列表的要求,但即使列表被调整,当我们对半分时,总有一半是完全排序的,我们依据这半部分来分析同样可以完成任务。比如示例 1 ,在列表中找目标 0,如下图:

我们先取中点,值为 7,此时左边正常排序,右边顺序有变。此时,判断目标不在正常排序的左边,所以将边界调整,直接取右半部分。

接下来再取中点,值为 0,此时右边正常排序,但中点的值已经是目标值了,任务结束,返回此刻中点左边即可。

类似地,我们每次取中点,找两边正常排序的部分,看目标是否位于该部分,然后调整边界缩小范围至一半,直至最终定位。

代码实现

在这段代码中,为了不纠结缩小范围换边界时究竟选用 mid 还是 mid+1、mid-1,我就单独把边界处可能取到目标值的情况也给做了处理,一旦检测到目标值,直接返回。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        length = len(nums)
        # 对空列表和只有一个数的列表特殊处理
        if length<2:
            if nums and nums[0]==target:
                return 0
            else:
                return -1
		# l 左边界,r 右边界
        l,r = 0,length-1
        # l 与 r 相等时结束循环
        while l<r:
        	# 取中值
            mid = (r+l)//2
            # 如果中值处为目标值,直接返回
            if nums[mid]==target:
                return mid
            # 如果边界处为目标值,也直接返回
            if nums[l]==target:
                return l
            if nums[r]==target:
                return r
            # 如果左边界小于中点的值,说明左部是正常排序
            if nums[l]<nums[mid]:
            	# 若此时目标值在左部,将右边界缩到 mid-1
                if nums[l]<target and target < nums[mid]:
                    r = mid-1
                # 否则调整左边界到 mid+1
                else:
                    l = mid+1
            # 右部正常排序的情况
            else:
            	# 若目标值位于右部,调整左边界到 mid+1
                if nums[mid]<target and target < nums[r]:
                    l = mid+1
                # 否则,调整右边界
                else:
                    r = mid-1
        # 若上述过程循环完仍未取到目标值,说明没有,返回 -1    
        return -1

提交测试表现:

执行用时 : 32 ms, 在所有 Python3 提交中击败了 97.01% 的用户
内存消耗 : 13.9 MB, 在所有 Python3 提交中击败了 7.69% 的用户

表现是挺亮眼的,接下来,会一会最费时间的题目。

题目三

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

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

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

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

题目分析

这道题很奇怪,你说它能用二分查找法吧,应该是能用的:排序列表,查找元素位置。但是要查目标值出现的起始和结束两个位置,这个要怎么做?

同时找两个位置肯定不好找,我们需要分步来:先用二分法查找起始位置。查完后,再从起始位置到列表结束,继续用二分法查找结束位置。

比如示例 1,先通过二分法定位到目标 8 的起点;再从该起点开始继续二分查找终点位置:

与之前不同的点在于,找起点位置过程中,即使取到的中点值与目标值相等,我们仍然要取左侧部分继续分析,因为我们要找的目标值的起点;同理,找结束位置时,即使取到的中点值与目标相等,我们仍要取右侧部分继续分析。

代码实现

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        # 特殊情况处理
        if length<2:
        	# 单数列表,且该数与目标值相等
            if nums and nums[0]==target:
                return [0,0]
            # 不匹配的单数列表、空列表
            else:
                return [-1,-1]
        # 目标值超出列表值范围情况
        if target<nums[0] or target>nums[-1]:
            return [-1,-1]
        # 先定义好默认值
        left,right = -1,-1
        # 起始位置的二分查找开始
        l,r = 0,length-1
        # 老样子,while 循环
        while l<r:
        	# 取中点
            mid = (l+r)//2
            # 若中点小于目标值,调整左边界至 mid+1
            # 因为取中点偏左边界,所以可以不取 mid 直接下一位 mid+1,即使 mid+1 真就是起始位置,也可以通过取中点取到该处
            if nums[mid]<target:
                l = mid+1
            # 若中点值大于等于目标,因为我们要找目标的起点,所以把右边界调整到 m
            # 不取 mid-1 的原因在于,若 mid-1 为起点,把其作为右边界的话,无法通过取中点定位到该位置
            elif nums[mid]>=target:
                r = mid
        # while 循环结束时,l 即起点位置,这时要检查下列表中该位置是否存在目标值
        # 若列表该位置确实存在目标值,更新起始位置到 left
        if nums[l]==target:
            left = l
        # 若不存在,列表中没有目标值,返回 -1 相关结果
        else:
            return [-1,-1]
		# 接下来找结束位置
		# 若此时已经是最后一位,那么结束位置与起始位置相同,直接返回
        if l+1==length:
            return [left,left]
        # 若后续还有其它位,重新开启二分查找
        # 取起始位置下一位开始作为边界
        l,r = l+1,length-1
        while l<r:
            mid = (l+r)//2
            # 如果中点值大于目标,更新右边界为 mid
            if nums[mid]>target:
                r = mid
            # 如果中点值小于等于目标,将左边界更新
            elif nums[mid]<=target:
                l = mid+1 
        # 当while循环结束时,有可能 l 是结束位置,也可能是结束位置的下一位
        # 若为结束位置          
        if nums[l]==target:
            right = l
        # 若其上一位是结束位置
        elif nums[l-1]==target:
            right = l-1
        # 将更新完毕的位置返回
        return[left,right]

最后求结束位置时还分情况讨论了下,按照我们区分边界的分析,最终求出的左边 l 应该是结束位置的下一位,结束位置应该是 l-1;但是若该列表以重复出现的目标值作为最后元素,比如 [1,2,2] 目标值为 2,又因为右边界的值无法通过中点取到,所以最终拿到的结束位置 l = 2,恰好也是目标值,所以也需要对这种情况下做一个判断处理。

提交测试表现:

执行用时 : 40 ms, 在所有 Python3 提交中击败了 81.86% 的用户
内存消耗 : 14.6 MB, 在所有 Python3 提交中击败了 7.69% 的用户

结论

经过三道题目两天的练习,就基本可以掌握二分查找的用法了。该算法麻烦的点在于取完中点值后对下一半部左右边界的取值,以及配合题意变换做一些特殊情况考虑处理。

乍一看会觉得一团糟,但理清思路后,便可以一步步完成代码了。当然,还是会有些问题,比如 34 题求最后结束位置时对不同情况的特殊处理,这个一般还挺难考虑到,得通过提交测试时返回的特殊例子来检查出漏洞予以修复。

今天 10:30-12:00,试着参与了下 LeetCode 周赛,4 道题只做出前两道,排名很惨烈。对于题目解法的储备不足,没有头绪是最浪费时间的,之后还要多加练习~

本文分享自微信公众号 - TTTEED(TEDxPY),作者:TED

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 第二轮 Python 刷题笔记一:数组

    经过四十多天缓慢的刷题,现在进度大概是刷了八十多道 LeetCode 题,最近也在吸取过来人的经验,仍然需要对刷题计划进行调整。

    TTTEED
  • 变换排列与最长括号—— LeetCode 第 31、32 题记

    LeetCode 算法题,更像是披着编程语法外衣的数学题,很多典型的问题都有较优的解题思路与方法。之前我都是先尽力硬磕,几个小时肝出个解法,然后匆匆写一篇题记,...

    TTTEED
  • Python 版 LeetCode 刷题笔记 #1 两数之和

    学 Python 也有一段时间了,一直维持在入门阶段,最近想集中精力精进下编码能力,所以把刷题当作一个练习,也看看自己能坚持几道题。

    TTTEED
  • LeetCode 81. Search in Rotated Sorted Array II

    二分的关键在于判断当前的中点 mid 是在数组旋转点的左边还是右边,当有重复的元素的时候,当nums[mid]==nums[l] && nums[mid]==n...

    ShenduCC
  • Leetcode 33 Search in Rotated Sorted Array 二分查找变式

    Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i....

    triplebee
  • Leetcode 81 Search in Rotated Sorted Array II

    Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed...

    triplebee
  • 剑指Offer - 面试题53 - I. 在排序数组中查找数字 I(二分查找的变形版本)

    类似题目:LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)

    Michael阿明
  • T11-搜索旋转排序数组

    今天分享leetcode第11篇文章,也是leetcode第33题—Search in Rotated Sorted Array(搜索旋转排序数组),地址是:h...

    木又AI帮
  • 【leetcode刷题】T12-搜索旋转排序数组II

    今天分享leetcode第12篇文章,也是leetcode第81题—搜索旋转排序数组II(Search in Rotated Sorted Array II),...

    木又AI帮
  • 每天一道leetcode-33

    目前准备每天刷一道题leetcode的题目,以此来激励那些零基础入门的人,千万不要被什么科班和非科班的说法吓倒了,计算机这个行业只要你肯努力,没有什么逾越不了的...

    乔戈里

扫码关注云+社区

领取腾讯云代金券