In this Leetcode Find First and Last Position of Element in Sorted Array Problem solution, Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must 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
Solution in C Programming
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
int * arr=(int*)malloc(sizeof(int)*2);
*returnSize=2;
arr[0]=-1;
arr[1]=-1;
int i=0,j=numsSize-1;
if(numsSize==0)return arr;
while(i<numsSize && nums[i]<target)i++;
while(j>=0 && nums[j]>target)j--;
if(i<numsSize && nums[i]==target)arr[0]=i;
if(j>=0 && nums[j]==target)arr[1]=j;
return arr;
}Solution in C++ Programming
class Solution {
public:
int bs(vector<int>& arr,int n,int k){
int lo=0;
int hi=n-1;
int res=-1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(arr[mid]==k){
res=mid;
hi=mid-1;
}
else if(arr[mid]<k){
lo=mid+1;
}
else{
hi=mid-1;
}
}
return res;
}
int fs(vector<int>& arr,int n,int k){
int lo=0;
int hi=n-1;
int res=-1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(arr[mid]==k){
res=mid;
lo=mid+1;
}
else if(arr[mid]<k){
lo = mid+1;
}
else {
hi=mid-1;
}
}
return res;
}
vector<int> searchRange(vector<int>& nums, int target) {
int n=bs(nums,nums.size(),target);
int k=fs(nums,nums.size(),target);
return {n,k};
}
};Solution in Java Programming
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[]{-1, -1};
if (nums == null || nums.length == 0) return result;
if (target > nums[nums.length - 1]) return result;
int left = 0;
int right = nums.length;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
left = mid;
while (left - 1 >= 0) {
if (nums[left - 1] == target) left--;
else break;
}
right = mid;
while (right + 1 < nums.length) {
if (nums[right + 1] == target) right++;
else break;
}
result[0] = left;
result[1] = right;
return result;
}
if (target > nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
}Solution in Python Programming
class Solution(object):
def searchRange(self, nums, target):
rangeVal = [-1, -1]
helper(nums, target, 0, len(nums) - 1,rangeVal, True)
helper(nums, target, 0, len(nums) - 1,rangeVal, False)
return rangeVal
def helper(array, target, left, right, rangeVal, goLeft):
while left <= right:
mid = (left + right) // 2
if array[mid] < target:
left = mid + 1
elif array[mid] > target:
right = mid - 1
else:
if goLeft:
if mid == 0 or array[mid - 1] != target:
rangeVal[0] = mid
break
else:
right = mid - 1
else:
if mid == len(array) - 1 or array[mid + 1] != target:
rangeVal[1] = mid
break
else:
left = mid + 1Solution in C# Programming
public class Solution {
public int[] SearchRange(int[] nums, int target) {
if(nums.Length == 0 || target < nums[0] || target > nums[nums.Length - 1]) return new [] {-1, -1};
int l = 0, r = nums.Length - 1;
while(l <= r){
var m = (l + r) / 2;
if(nums[m] == target){
int i = m, j = m;
while(i >= 0 && nums[i] == target) i--;
while(j < nums.Length && nums[j] == target) j++;
return new [] {i + 1, j - 1};
}
if(target > nums[m])
l = m + 1;
else
r = r - 1;
}
return new [] {-1, -1};
}
}Also read,