First And Last Position of Element In Sorted Array: 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 :
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Table of Contents
First And Last Position of Element In Sorted Array Problem Solution
Problem Solution In Python
class Solution:
def searchRange(self, nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target)
return [left, right - 1]
Problem Solution In Java
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = 0;
int end = nums.length-1;
int first =-1;
while(start<=end){
int mid = (start+end)/2;
if(nums[mid]==target)first = mid;
if(nums[mid]>=target)end = mid-1;
else start =mid+1;
}
int last = -1;
start=0;end =nums.length-1;
while(start<=end){
int mid = (start+end)/2;
if(nums[mid]==target)last = mid;
if(nums[mid]>target)end = mid-1;
else start =mid+1;
}
return new int[]{first,last};
}
}
Problem Solution In C++
int bs(vector<int> &nums, int target, int left, int right) { // binary search
while (left < right) {
int mid = (right + left) / 2;
if (nums[mid] == target && (mid == 0 || nums[mid - 1] != target))
return mid;
else if (nums[mid] >= target)
right = mid;
else
left = mid + 1;
}
return left;
}
vector<int> searchRange(vector<int>& nums, int target) {
int l = bs(nums, target, 0, nums.size());
if (l == nums.size() || nums[l] != target)
return {-1, -1};
int r = bs(nums, target + 1, l, nums.size()) - 1;
return {l, r};
}
Problem Solution In C
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
*returnSize=2;
int * result=(int*)malloc(sizeof(int)*2);
result[0]=-1;
result[1]=-1;
int start=-1;
int end=-1;
if(numsSize==0)
{
return result;
}
for(int i=0;i<numsSize;i++)
{
if(nums[i]==target)
{
start=i;
break;
}
}
for(int i=numsSize-1;i>=0;i--)
{
if(nums[i]==target)
{
end=i;
break;
}
}
result[0]=start;
result[1]=end;
return result;
}