leetcode34 在排序数组中查找元素的第一个位置和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

示例 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最左边的索引，以及在有序数组中查找target+1最左边的索引，这样只需要一个函数就可以搞定了。

public int[] searchRange(int[] nums, int target) {int[] ans={-1,-1};int left=getLeft(nums,target);//如果left==nums.length代表target大于给出数组nums的最大元素，或者//nums[left]!=target，代表找不到target直接返回{-1,-1}即可if(left>=nums.length || nums[left]!=target){return ans;}ans[0]=left;//找到target+1所在的第一个元素或者应该插入的位置，再减去1得到target的最右边所在的索引ans[1]=getLeft(nums,target+1)-1;return ans;}//得到target在有序数组中最左边的索引位置，如果不存在，则找到应该插入的位置。public int getLeft(int[] nums,int target){int left=0;int right=nums.length-1;//索引范围是[left,right],所以这边要<=，不漏掉left==right,即mid=left=right这个索引。while(left<=right){int mid=(left+right)>>1;//要往左边逼近，因为此时的nums[mid]不一定是最左边等于target的索引，索引位置的数如果等于target，我们就要让right=mid-1,继续往左逼近。if(nums[mid]>=target){right=mid-1;}else{left=mid+1;}}//这边一定返回left，不能返回right，这边的原因大家可以带一个例子走个流//程，或者看二分搜索专栏里之前的题目return left;}//函数getLeft()和函数getLeft2()作用是相同的，只不过写法不同，可以对比看。public int getLeft2(int[] nums,int target){int left=0;int right=nums.length;while(left<right){int mid=(left+right)>>1;//如果nums[mid]==target，right还要往前推，因为right可能不//是最左边等于target的索引，这边必须right=mid,不是//right=mid-1,因为一开始选的索引范围是包左不包右即//[left,right),所以right=mid;if(nums[mid]>=target){right=mid;}else{left=mid+1;}}return left;}

如果觉得《6 leetcode34 在排序数组中查找元素的第一个位置和最后一个位置**》对你有帮助，请点赞、收藏，并留下你的观点哦！