【Java】【LeecCode34】在排序数组中查找元素的第一个和最后一个位置

本题使用官方视频题解，只用于记录自己刷leetcode的理解和题解（第34题）

由于在做二分法题目的时候，先看有序数组，无重复元素，一般来说就可以二分，在34题的时候，怎么处理逻辑问题是个考验。

要返回第一个元素和最后一个元素，我们就分开来找

**先找左边：**

private int findfirst(int[] nums,int target){int left = 0;int right = nums.length-1;while (left<right){//退出循环的时候l==rint mid = left +(right - left)/2;if(nums[mid]<target){//中间以及中间左边元素一定不是元素出现的第一个位置[0 1 2 2] 2left = mid+1;}else if(nums[mid] == target){//只能说明中间以及中间右边元素可能不是元素出现的第一个位置[1 1 2 2 2] 2//那么搜索区间就变成了[left mid]right = mid;}else{//nums[mid]> target mid以及mid右边一定不是目标元素出现的第一个位置 [1 1 2 2 2] 1right = mid -1;}}if(nums[left] == target){//退出循环的时候left == right 但是不能保证数组有这个元素return left;}return -1;}

**再找右边：**

private int findlast (int[] nums,int target){int left = 0;int right = nums.length-1;while (left<right){//退出循环的时候l==rint mid = left +(right - left)/2;//int mid = (left + right +1) >>> 1; 不清楚 向上取整if(nums[mid]<target){//中间以及中间左边元素一定不是元素出现的最后一个位置[0 1 2 2] 2left = mid+1;}else if(nums[mid] == target){//只能说明中间以及中间右边元素可能不是元素出现的最后一个位置[1 1 2 2 2] 2//那么搜索区间就变成了[mid right]left = mid;}else{//nums[mid]> target mid以及mid右边一定不是目标元素出现的最后一个位置 [1 1 2 2 2] 1right = mid -1;}}//不需要判断是因为左边如果没有 那么就没有 return left;}

左右都找到了，但是算法题怎么去找边界条件很重要，在做软件开发测试的时候就会拿边界条件来测试 = - =

就是考虑 如果数组长度为0怎么办？如果长度不为0，但是数组中没有这个元素怎么办？

长度为0 就返回 {-1，-1}

数组中没有，也是返回{-1，-1}

找到判断条件

if(len == 0) return new int[]{-1,-1};//数组长度为0

数组中没有这个元素，在找左边界就已经搞定了，如果左边界都没有找到，那么肯定没有啦

所以，完整视频题解如下：

class Solution {public int[] searchRange(int []nums,int target){int len = nums.length;if(len == 0) return new int[]{-1,-1};int first = findfirst(nums,target);if(first == -1) return new int[]{-1,-1};int last = findlast(nums,target);return new int[]{first,last};}private int findfirst(int[] nums,int target){int left = 0;int right = nums.length-1;while (left<right){//退出循环的时候l==rint mid = left +(right - left)/2;if(nums[mid]<target){//中间以及中间左边元素一定不是元素出现的第一个位置[0 1 2 2] 2left = mid+1;}else if(nums[mid] == target){//只能说明中间以及中间右边元素可能不是元素出现的第一个位置[1 1 2 2 2] 2//那么搜索区间就变成了[left mid]right = mid;}else{//nums[mid]> target mid以及mid右边一定不是目标元素出现的第一个位置 [1 1 2 2 2] 1right = mid -1;}}if(nums[left] == target){//退出循环的时候left == right 但是不能保证数组有这个元素return left;}return -1;}private int findlast (int[] nums,int target){int left = 0;int right = nums.length-1;while (left<right){//退出循环的时候l==rint mid = left +(right - left)/2;//int mid = (left + right +1) >>> 1; 不清楚 向上取整if(nums[mid]<target){//中间以及中间左边元素一定不是元素出现的最后一个位置[0 1 2 2] 2left = mid+1;}else if(nums[mid] == target){//只能说明中间以及中间右边元素可能不是元素出现的最后一个位置[1 1 2 2 2] 2//那么搜索区间就变成了[mid right]left = mid;}else{//nums[mid]> target mid以及mid右边一定不是目标元素出现的最后一个位置 [1 1 2 2 2] 1right = mid -1;}}//不需要判断是因为左边如果没有 那么就没有 开始已经判断了return left;}}

但是本题不能AC，我也不太清楚，是超时长限制了，但是要清楚每一步的思维和理解，下次遇到类似的题目或者想法都可以用上！