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&nbsp;write an algorithm with&nbsp;O(log n) runtime complexity.

&nbsp;
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]

&nbsp;
Constraints:


	0 &lt;= nums.length &lt;= 105
	-109&nbsp;&lt;= nums[i]&nbsp;&lt;= 109
	nums is a non-decreasing array.
	-109&nbsp;&lt;= target&nbsp;&lt;= 109


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # if target is not in nums list, we simply return [-1,-1]
		if target not in nums:
            return [-1,-1]
        
		# create an empty list
        result = []
		# iterate nums for the first time, if we found nums[i] matches with target
		# append the index i to result, break the for loop
		# because we only care the first and last index of target in nums
        for i in range(len(nums)):
            if nums[i] == target:
                result.append(i)
                break
        
		# loop through nums backward, if we found nums[j] matches target
		# append j to result and break the for loop
        for j in range(len(nums)-1, -1, -1):
            if nums[j] == target:
                result.append(j)
                break
        
        return result
		
		
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans={-1,-1}; 
        int start=search(nums,target,true);
        int end=search(nums,target,false);
        ans[0]=start;
        ans[1]=end;
        return ans;
    }
    int search(int[] nums ,int target,boolean findStart){
        int ans=-1;
        int start=0;
        int end=nums.length-1;
        while(start<=end){
         int  mid=start+(end-start)/2;
            if(target>nums[mid]){
           start=mid+1;
            }
            else if(target<nums[mid]){
                end=mid-1;
            }
            else{
                ans=mid;
                if(findStart){
                    end=mid-1;
                }
                else{
                    start=mid+1;
                }
            }
        }
        return ans;
    }
}
class Solution {
public:

    int startEle(vector<int>& nums, int target,int l,int r)
    {
        while(l<=r)
        {
            int m = (l+r)/2;
            if(nums[m]<target) l=m+1;
            else if(nums[m]>target) r = m-1;
            else
            {
                if(m==0)
                    return m;
                else if(nums[m-1]==target)
                    r = m-1;
                else
                    return m;
            }
        }

        return -1;
    }

     int lastEle(vector<int>& nums, int target,int l,int r)
    {
        while(l<=r)
        {
            int m = (l+r)/2;
            if(nums[m]<target) l=m+1;
            else if(nums[m]>target) r = m-1;
            else
            {
                if(m==nums.size()-1)
                    return m;
                else if(nums[m+1]==target)
                    l = m+1;
                else
                    return m;
            }
        }

         return -1;
    }
    vector<int> searchRange(vector<int>& nums, int target) {

        vector<int> binSearch;
        int a = startEle(nums,target,0,nums.size()-1);
        if(a==-1)
        {
             binSearch.push_back(-1);
             binSearch.push_back(-1);
            return binSearch;
        }
        else
        {
            binSearch.push_back(a);
        }

        int b = lastEle(nums,target,0,nums.size()-1);
        binSearch.push_back(b);

        return binSearch;

    }
};
var searchRange = function(nums, target) {
    if (nums.length === 1) return nums[0] === target ? [0, 0] : [-1, -1];
    
    const findFirstInstance = (left, right) => {
        if (left === right) return left;
        var pivot;
        while (left < right) {
            if (left === pivot) left += 1;
            pivot = Math.floor((left + right) / 2);
            if (nums[pivot] === target) {
                if (nums[pivot - 1] !== target) return pivot;
                return findFirstInstance(left, pivot - 1);
            }
            if (nums[pivot] > target) right = pivot;
            else left = pivot;
        }
    }
    const findLastInstance = (left, right) => {
        if (left === right) return left;
        var pivot;
        while (left < right) {
            if (left === pivot) left += 1;
            pivot = Math.floor((left + right) / 2);
            if (nums[pivot] === target) {
                if (nums[pivot + 1] !== target) return pivot;
                return findLastInstance(pivot + 1, right);
            }
            if (nums[pivot] > target) right = pivot;
            else left = pivot;
        }
    }
    
    var left = 0,
        right = nums.length - 1,
        pivot;
    
    while (left < right) {
        if (left === pivot) left += 1;
        pivot = Math.floor((left + right) / 2);
        if (nums[pivot] === target) {
            var first = nums[pivot - 1] !== target ? pivot : findFirstInstance(left, pivot - 1);
            var last = nums[pivot + 1] !== target ? pivot : findLastInstance(pivot + 1, right);
            return [first, last];
        }
        if (nums[pivot] > target) right = pivot;
        else left = pivot;
    }
    
    return [-1, -1];
};
Find First and Last Position of Element in Sorted Array