今天仍然做二分查找相关的题目。先来回顾一下二分查找的方法和使用的条件。二分查找是在数组中查找目标值的一种方法，通过边界索引确定中间索引，判断中间索引处的元素值和目标值的大小，来不断缩小查找区间。使用二分查找有如下一些限制：

• 数组是单调递增或单调递减；
• target值唯一。

话不多说，直接上题！

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]

解法一：我自己写出来的！明天奖励自己吃个鸡腿，哈哈哈哈
主要思路：
  首先题目中给定的数组是非减顺序，其实不符合二分查找的条件，但是题目最终是要找到等于target的开始位置和结束位置。这里可以分为三种情况：
  (1) target不在数组中，则和普通的二分查找方式一样；
  (2) target在数组中，但有且仅有一个，那也和普通的二分查找一样；
  (3) target在数组中，但个数不止一个，这种情况下当nums[mid] == target时，首先就可以把mid存储起来，其次因为在当前这个区间内不止一个target，所以不能按照以前的方式直接返回或确定当前mid左侧的值一定全部小于target，mid右侧的值一定全部大于target。故这里就会以mid为节点，分成两个子区间[lindex，mid-1]和[mid+1，rindex]，两个子区间分别再进行二分查找，寻找满足条件的索引。

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:# 设定一个list，用来存储数组中等于target的索引# 且out要么为空要么有且仅有两个元素，包括左边界和右边界out=[]  def run(lindex,rindex):if lindex > rindex:return -1mid=lindex+(rindex-lindex)//2# 当mid索引元素不等于target时，像之前普通二分查找法一样if nums[mid] != target:if nums[mid]>target:rindex=mid-1else:lindex=mid+1return run(lindex,rindex)# 当mid索引元素==target时else:if len(out) == 0:# 若当前mid是第一个判断为target的索引，则填充至outout.extend([mid,mid]) else:# 当满足条件的索引大于1个时，# 则这里判断当前索引是左边界还是右边界out[0]=min(out[0],mid)out[1]=max(out[1],mid)# 当mid索引==target时，需将[lindex,rindex]划分成两个子区间# 分别进行二分查找，继续搜索==target的索引run(lindex,mid-1)run(mid+1,rindex)run(0,len(nums)-1)if len(out) == 0:return [-1,-1]return out

解法二：看的代码随想录的解法，可以学习这种思路
解题思路：
  这里使用两次二分法分别去查找target的左边界和右边界(特别注意的是，这里的左边界指的是第一个target索引的前面一位索引，右边界也是一样)，也可以分为三种情况去讨论，分别是：
  (1) target小于数组的最小值或大于数组的最大值，即在数组范围的左侧或右侧；
  (2) target在数组范围内，但target不在数组中；
  (3) target在数组中。

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:# 获得右边界def  getRightBorder(nums,target):rightBorder=-2lindex=0rindex=len(nums)-1while lindex<=rindex:mid=lindex+(rindex-lindex)//2if nums[mid] > target:rindex=mid-1else:lindex=mid+1rightBorder=lindex  # 这里右边界更新return rightBorder# 获得左边界def getLeftBorder(nums,target):leftBorder=-2lindex=0rindex=len(nums)-1while lindex<=rindex:mid=lindex+(rindex-lindex)//2if nums[mid] >= target:rindex=mid-1leftBorder=rindex  # 这里左边界更新else:lindex=mid+1  return leftBorder            leftBorder = getLeftBorder(nums,target)rightBorder = getRightBorder(nums,target)# 情况一，target不在数组范围内时，以target在数组左侧为例，# 二分查找会不断更新rindex的值，那么leftBorder不更新，一直为-2。同理可以推出，target在数组右侧的情况。if leftBorder == -2 or rightBorder == -2:return [-1,-1]# 情况三，因为leftBorder和rightBorder分别位于target的前一个索引位置和后一个索引位置# 故 rightBorder-leftBorder必定大于1elif rightBorder-leftBorder > 1:return [leftBorder+1,rightBorder-1]# 情况二else:return [-1,-1]

参考

代码随想录-34. 在排序数组中查找元素的第一个和最后一个位置