https://leetcode.com/problems/search-for-a-range/description/
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
1 public int[] searchRange(int[] nums, int target) { 2 //corner case: 3 if(nums == null || nums.length == 0) return new int[]{-1,-1}; 4 5 /*question to ask: if there is only one item in the array, then return new int[]{index, index} 6 */ 7 int left = 0, right = nums.length -1 ; 8 //find the 1st occurance 9 int firstIndex = findFirst(nums, target); 10 //find the last occurance 11 int lastIndex = findLast(nums, target); 12 return new int[]{firstIndex, lastIndex} ; 13 }14 private int findFirst (int[] nums, int target){15 int left = 0 , right = nums.length - 1 ; 16 while(left + 1< right){17 int mid = left + (right - left)/2 ; 18 if(nums[mid] == target){19 right = mid ; 20 } else if(nums[mid] < target){21 left = mid ; 22 } else {23 right = mid ; 24 }25 }26 //post processing: first occurance 27 if(nums[left] == target){28 return left ; 29 }30 if(nums[right] == target){31 return right ; 32 }33 return -1 ; 34 }35 36 private int findLast (int[] nums, int target){37 int left = 0 , right = nums.length - 1 ; 38 while(left + 1< right){39 int mid = left + (right - left)/2 ; 40 if(nums[mid] == target){41 left = mid ; 42 } else if(nums[mid] < target){43 left = mid ; 44 } else {45 right = mid ; 46 }47 }48 //post processing: first occurance 49 if(nums[right] == target){50 return right ; 51 }52 if(nums[left] == target){53 return left ; 54 }55 return -1 ; 56 }