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.

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