大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位脉友透露小红书给部分员工发了年中奖，据说绩效3.75给了两个月，貌似这次年中奖只向绩效比较好的3.5+以及3.75的员工发放，不少内部员工纷纷表示要为小红书卖命。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「在排序数组中查找元素的第一个和最后一个位置」。
题目描述
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
思路解析
最简单直观的方法就是遍历一遍数组记录target的起始位置和结束位置，这种方法的时间复杂度为O(n)，题目要求时间复杂度为O(logn)。
给定的数组是有序的，还要求时间复杂度为O(logn)，自然而然就想到二分查找。这里我们寻找target对应的左右边界需要进行两次二分查找。
假设给定的nums = [5,7,7,8,8,10]，target = 8，下面来看下寻找8对应左边界的过程。
初始化left=0， right=5， 中间位置mid=2对应的元素小于target=8，所以我们需要去mid右边绿色的区域寻找target。
当前mid位置的值等于target=8，我们记录下当前的索引index=4。然后继续去mid左边查找target。
当前mid位置的值等于target=8，更新index=3，继续去mid左边查找target。。
此时left>right，我们就拿到了左边界的索引index。
查找右边界和查找左边界类似，下面我们给出c++和python两种代码实现。
C++代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = binSearch(nums, target, true);
int right = binSearch(nums, target, false);
return {left, right};
}
//isLeft表示是否寻找左边界
int binSearch(vector<int>& nums, int target, bool isLeft) {
int left = 0, right = nums.size() - 1;
int index = -1;
while (left <= right) {
int mid = (left + right)/2;
//mid位置的值比目标值大，需要去mid左边寻找目标值
if (nums[mid] > target) {
right = mid - 1;
//mid位置的值比目标值小，需要去mid右边寻找目标值
} else if (nums[mid] < target) {
left = mid + 1;
} else {
//找到目标值,先记录下当前的索引
index = mid;
if (isLeft) {
//如果寻找左边界，需要继续去mid左边更新index的值
right = mid - 1;
} else {
//如果寻找右边界，需要继续去mid右边更新index的值
left = mid + 1;
}
}
}
return index;
}
};
python代码
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left = self.binSearch(nums, target, True)
right = self.binSearch(nums, target, False)
return [left, right]
# isLeft表示是否寻找左边界
def binSearch(self, nums, target, isLeft):
left, right = 0, len(nums) - 1
index = -1
while left <= right:
mid = (left + right) // 2
# mid位置的值比目标值大，需要去mid左边寻找目标值
if nums[mid] > target:
right = mid - 1
# mid位置的值比目标值小，需要去mid右边寻找目标值
elif nums[mid] < target:
left = mid + 1
else:
# 找到目标值,先记录下当前的索引
index = mid
if isLeft:
# 如果寻找左边界，需要继续去mid左边更新index的值
right = mid - 1
else:
# 如果寻找右边界，需要继续去mid右边更新index的值
left = mid + 1
return index
复杂度分析
时间复杂度： 整个过程使用了二分查找，时间复杂度为O(logn)。
空间复杂度： 只用到了几个额外的变量，空间复杂度为O(1)。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
