First And Last Position of Element In Sorted Array Problem Solution

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]

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;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment