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, print[-1, -1].

You must write an algorithm with O(log n) runtime complexity.

### Input Format

The first line contains two integers n (number of elements in the array) and target.

The second line contains n integers (value of elements in the array).

### Output Format

Print two space separated integers denoting the first and last index of target.

### Example 1

**Input**

6 8 5 7 7 8 8 10

**Output**

3 4

**Explanation**

8 occurs for the first time at index 3 and at index 4 for the last time.

### Example 2

**Input**

6 6 5 7 7 8 8 10

**Output**

-1 -1

**Explanation**

6 doesn’t occur in the given array, hence we return -1 -1

### Constraints

0 <= nums.length <= 10^5

-10^9 <= nums[i] <= 10^9

nums is a non-decreasing array.

-10^9 <= target <= 10^9

## Solution of Find First and Last Position of Element in Sorted Array in java:–

import java.util.*; import java.lang.*; import java.io.*; public class Main { public static int[] searchRange(int[] arr, int target) { int ans[] = new int[2]; ans[0] = firstOccurance(arr, target); ans[1] = lastOccurance(arr, target); return ans; } static int firstOccurance(int[] arr, int target) { int l = 0; int r = arr.length - 1; int ans = -1; int mid; while(l <= r) { mid = (l + r)/2; if(arr[mid] == target) { ans = mid; r = mid - 1; } else if(arr[mid] < target) { // set the starting point correctly l = mid + 1; } else if(arr[mid] > target) { // update the end of subarray r = mid - 1; } } return ans; } static int lastOccurance(int[] arr, int target) { int n = arr.length; int mid; int l = 0; int r = arr.length - 1; while(l <= r) { mid = (l + r)/2; if(arr[mid] == target) { if(mid == n - 1 || arr[mid + 1] != target) return mid; l = mid + 1; // reduce the array to half } else if(arr[mid] < target) { // set the starting point correctly l = mid + 1; } else if(arr[mid] > target) { // update the end of subarray r = mid - 1; } } return -1; } public static void main (String[] args) throws java.lang.Exception { //your code here Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int arr[] = new int[n]; for(int i=0;i<n;i++) { arr[i]=sc.nextInt(); } int mat[]=searchRange(arr, k); for(int i=0;i<mat.length;i++) { System.out.print(mat[i]+" "); } } }

## Add a Comment