【Leetcode刷题Python】34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)

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]

2 解析

（1）方法一 两次二分查找 第一次查找起始位置:

1、二分的范围，l = 0l=0， r = nums.size() - 1r=nums.size()−1，我们去二分查找>=target>=target的最左边界。 2、当nums[mid] >= targetnums[mid]>=target时，往左半区域找，r = midr=mid。

3、当nums[mid] < targetnums[mid]=target>=target的位置LL。 第二次查找结束位置： 1、二分的范围，l = 0l=0， r = nums.size() - 1r=nums.size()−1，我们去二分查找