来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
题目描述
给定一个按照升序排列的整数数组 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]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
解题思路
题目中限制时间复杂度为O(logn)，那么很容易想到二分法，通过在二分法中更改等于时候的策略，就可以很简单求出上界和下界了，但是要注意边界样例。
代码展示
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int iLeft = 0, iRight = nums.size() - 1, iRetLeft = -1, iRetRight = -1; if(nums.size() == 0) return {iRetLeft, iRetRight}; while(iLeft <= iRight) { int mid = (iLeft + iRight) >> 1; if(nums[mid] < target) { iLeft = mid + 1; } else { iRight = mid - 1; } } if(iLeft >= 0 && iLeft < nums.size() && nums[iLeft] == target) iRetLeft = iLeft; iLeft = 0, iRight = nums.size() - 1; while(iLeft <= iRight) { int mid = (iLeft + iRight) >> 1; if(nums[mid] <= target) { iLeft = mid + 1; } else { iRight = mid - 1; } } if(iRight >= 0 && iRight < nums.size() && nums[iRight] == target) iRetRight = iRight; return {iRetLeft, iRetRight}; } };
运行结果
![[leetcode~dfs]1261. 在受污染的二叉树中查找元素](https://ucc.alicdn.com/pic/developer-ecology/okfcmqqjwxoec_335a965e888346009ec98ec28a431196.png?x-oss-process=image/resize,h_160,m_lfit)