1.自己的解法，二分法，但是比较笨
class Solution { public int[] searchRange(int[] nums, int target) { if(nums.length==0) return new int[]{-1,-1}; int left=0,right=nums.length-1; int[] res = new int[2]; while(left<right&&(nums[left]!=target||nums[right]!=target)){ int mid=(left+right)/2; if(nums[mid]>target) right=mid-1; else if(nums[mid]<target) left=mid+1; else if(nums[mid]==target){ if((mid>0&&nums[mid-1]<target)||mid==0) left=mid; else if(nums[left]!=target) left++; if((mid<nums.length-1&&nums[mid+1]>target)||mid==nums.length-1) right=mid; else if(nums[right]!=target) right--; } } if(nums[left]!=target){ res[0]=-1; res[1]=-1; return res; } res[0]=left; res[1]=right; return res; } }以上方法感觉就是在硬找
2.优化后的二分法
class Solution { public int[] searchRange(int[] nums, int target) { if(nums.length==0) return new int[]{-1,-1}; int left=0,right=nums.length-1,mid=0; int[] res = new int[2]; while(left<=right){ mid=(left+right)/2; if(nums[mid]==target) break; else if(nums[mid]<target) left=mid+1; else right=mid-1; } if(nums[mid]!=target){ res[0]=-1; res[1]=-1; return res; } left=mid-1; right=mid+1; while(left>=0&&nums[left]==target){ left--; } while(right<nums.length&&nums[right]==target){ right++; } res[0]=left+1; res[1]=right-1; return res; } }
这种方法就是先用二分法找到一个mid ，使得nums[mid]==target
然后用这个mid，向mid的左右延伸
