Find First and Last Position of Element in Sorted Array in java

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

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
{
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]+" ");
}

}
}```