34. 在排序数组中查找元素的第一个和最后一个位置-LeetCode
心得:简单,二分查找,然后两个指针向两边扩散。
代码:
1 class Solution { 2 public int[] searchRange(int[] nums, int target) { 3 if(nums==null||nums.length==0) 4 { 5 return new int[]{-1,-1}; 6 } 7 int index=binaryFind(nums,0,nums.length-1,target); 8 int left=index; 9 int right=index; 10 if(index==-1) 11 return new int[]{-1,-1}; while(right<nums.length&&nums[index]==nums[right]) 12 right++; 13 while(left>=0&&nums[index]==nums[left]) 14 left--; 15 return new int[]{left+1,right-1}; 16 } 17 public int binaryFind(int[] nums,int left,int right,int target ) 18 { 19 int center=(left+right)>>>1; 20 if(left<=right) 21 { 22 if(nums[center]==target) 23 return center; 24 else if(target>nums[center]) 25 return binaryFind(nums,center+1,right,target); 26 else 27 return binaryFind(nums,left,center-1,target); 28 } 29 return -1; 30 } 31 }