吃透二分查找—— 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 道题只做出前两道，排名很惨烈。对于题目解法的储备不足，没有头绪是最浪费时间的，之后还要多加练习～