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