你下班了，是立刻回家还是会再待一会？相信大家肯定都是马上飞奔回家吧，再待一会干嘛，上班上出瘾了吗？然而，一网友就发帖提问：为什么公司那么多同事（尤其是Leader），晚上宁愿在工位刷抖音也不下班回家呢？
帖子下面，热爱评论的宝子们为我们解惑了。有人直接说：“据观察，有的是不想回家带小孩儿，有的是单身狗不想回狭小的出租屋”
还有人说：“因为回家只有空荡荡的房间 在公司省电费”区区几个字，越看越心酸。
另一边，还有人开玩笑：“等着家里老婆完事，不想回去撞到尴尬。”啊这...
更有人直言：“我之前问过我们公司一个领导，他跟我说等我到了他那个年纪，你就知道了”
这也反映出了一种生活状态：在外面各种当牛马，回家还要面对各种压力，所以，不回家就成了最简单的逃避方式。
但不管怎样，生活还得继续，希望大家都能找到属于自己的调味剂。毕竟，生活不止眼前的苟且，还有诗和远方，不是吗？那么你们觉得又是为什么呢？
下面是今日的大厂算法题
今日算法题，来自LeetCode的第34题：在排序数组中查找元素的第一个和最后一个位置，下面是我的算法思路及实现，让我们来看看吧。
算法题目
给定一个按照升序排列的整数数组 nums 和一个目标值 target，找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法。
👉点击领取 Go后端开发资料合集
算法思路
本题可以通过二分查找算法进行两次查找来解决：
第一次二分查找定位到目标值的开始位置：
如果 mid 对应的值大于或等于 target，移动右边界 right 到 mid。
否则，移动左边界 left 到 mid + 1。
最终，左边界 left 将指向目标值的开始位置。
第二次二分查找定位到目标值的结束位置： 如果 mid 对应的值小于或等于 target，移动左边界 left 到 mid + 1。
否则，移动右边界 right 到 mid。
最终，右边界 right 将指向目标值的结束位置的下一个位置，所以目标值的结束位置实际上是 right - 1。
在每次查找过程中，都需要检查边界条件，确保不会出现越界的情况。
func searchRange(nums []int, target int) []int {findFirstPosition := func() int {left, right := 0, len(nums)-1for left <= right {mid := left + (right-left)/2if nums[mid] < target {left = mid + 1} else {right = mid - 1}}if left < len(nums) && nums[left] == target {return left}return -1}findLastPosition := func() int {left, right := 0, len(nums)-1for left <= right {mid := left + (right-left)/2if nums[mid] <= target {left = mid + 1} else {right = mid - 1}}if right >= 0 && nums[right] == target {return right}return -1}return []int{findFirstPosition(), findLastPosition()}}
Java实现
public int[] searchRange(int[] nums, int target) {int[] result = new int[]{-1, -1};result[0] = findFirstPosition(nums, target);result[1] = findLastPosition(nums, target);return result;}private int findFirstPosition(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}if (left < nums.length && nums[left] == target) return left;return -1;}private int findLastPosition(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;} else {right = mid - 1;}}if (right >= 0 && nums[right] == target) return right;return -1;}
JavaScript实现
function searchRange(nums, target) {function findFirstPosition() {let left = 0, right = nums.length - 1;while (left <= right) {let mid = Math.floor((left + right) / 2);if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}if (nums[left] === target) return left;return -1;}function findLastPosition() {let left = 0, right = nums.length - 1;while (left <= right) {let mid = Math.floor((left + right) / 2);if (nums[mid] <= target) {left = mid + 1;} else {right = mid - 1;}}if (nums[right] === target) return right;return -1;}return [findFirstPosition(), findLastPosition()];}
算法解析
这种方法利用了二分查找的高效查找能力，在对数组进行两次二分查找后，能够精确地找到目标值的开始和结束位置。
通过调整左右边界的移动策略，我们可以分别定位到目标值的首次和最后一次出现的位置，从而实现了在 O(log n) 时间复杂度内解决问题的目标。
对于数组 nums = [5,7,7,8,8,10] 和目标值 target = 8：
第一次查找定位到开始位置，结果为 3。
第二次查找定位到结束位置，结果为 4。
因此，函数返回 [3, 4]。
因此，在使用二分查找之前，应先考虑数据是否满足这一条件，或者是否有必要先进行排序。同时，也要考虑排序本身的成本是否可接受，因为在某些情况下，排序的时间复杂度可能会抵消二分查找带来的效率提升。
热门推荐
发表评论:
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。