LeetCode [34] Search for a Range

 34. Find First and Last Position of Element in Sorted Array

Medium

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

 

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int n = nums.size(); vector<int> res(2, -1); int l = 0, r = n-1; while(l<=r){ int m = (l+r)/2; int mv = nums[m]; if(mv==target&&(m==0||nums[m-1]<target)){ res[0] = m; break; }else if(mv<target){ l = m+1; }else{ r = m-1; } } l = 0, r = n-1; while(l<=r){ int m = (l+r)/2; int mv = nums[m]; if(mv==target&&(m==n-1||nums[m+1]>target)){ res[1] = m; break; }else if(mv>target){ r = m-1; }else{ l = m+1; } } return res; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

class Solution { public int[] searchRange(int[] nums, int target) { int[] ret = new int[2]; ret[0] = -1; ret[1] = -1; int n = nums.length; int l = 0, r = n-1; while(l<=r){ int m = (l+r)/2; if(nums[m]==target && (m==0 || nums[m-1]<target)){ ret[0] = m; break; }else if(nums[m]<target){ l = m+1; }else{ r = m-1; } } l = 0; r = n-1; while(l<=r){ int m = (l+r)/2; if(nums[m]==target && (m==n-1 || nums[m+1]>target)){ ret[1] = m; break; }else if(nums[m]>target){ r = m-1; }else{ l = m+1; } } return ret; } }