34. Find the first and last positions of elements in a sorted array

Difficulty: medium

Given an array of integers in ascending order, nums, and a target value, target. Find the starting and ending positions of the given target value in the array.

If no target value exists in the array, return [-1, -1].

Advanced:

  • You can design and implement a time complexity of zeroO(log n)Does the algorithm solve this problem?

Example 1:

Input: nums = [5,7,7,8,8,10] target = 8Copy the code

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6Copy the code

Example 3:

Input: nums = [], target = 0 output: [-1,-1]Copy the code

Tip:

  • 0 <= nums.length <= 10<sup>5</sup>
  • -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
  • numsIs a non-decrement array
  • -10<sup>9</sup> <= target <= 10<sup>9</sup>

Solution

Language: java

class Solution { public int[] searchRange(int[] nums, int target) { if(nums == null || nums.length == 0) return new int[]{-1 , -1}; int findFirstPosition = findFirstPosition(nums, target); int findLastPosition = findLastPosition(nums, target); return new int[]{findFirstPosition , findLastPosition}; @param target * @param target * @return */ private int findLastPosition(int[] nums, int target) { int start = 0; int end = nums.length - 1; while(start <= end) { int mid = start + (end - start) / 2; if(nums[mid] == target) { if(mid == nums.length - 1 || nums[mid + 1] ! = target) { return mid; } else { start = mid + 1; } } else if(nums[mid] > target) { end = mid - 1; } else{ start = mid + 1; } } return -1; * @param target * @return */ private int findFirstPosition(int[] nums, int target) { int start = 0; int end = nums.length - 1; while(start <= end) { int mid = start + (end - start) / 2; if(nums[mid] == target) { if(mid == 0 || nums[mid - 1] ! = target) { return mid; } else { end = mid - 1; } } else if(nums[mid] > target) { end = mid - 1; } else{ start = mid + 1; } } return -1; }}Copy the code