Search for a range in java

Search for a range in java

Given a sorted array of integers A(0 based index) of size N, find the starting and ending position of a given integar B in array A.

Your algorithm’s runtime complexity must be in the order of O(log n).

Print 2 integers separated by space, such that first element = starting position of B in A and second element = ending position of B in A, if B is not found in A print -1 -1.

Input Format

The first line given is N, denoting the size of array A. The second line given is the integer array A. The third line given is the integer B.

Output Format

Print 2 integers, such that first element = starting position of B in A and second element = ending position of B in A, if B is not found in A print -1 -1.

Constraints

1 <= N <= 10^6 1 <= A[i], B <= 10^9

For Example

Input 1: 6 5 7 7 8 8 10 8 Output 1: 3 4

Explanation 1: First occurence of 8 in A is at index 3 Second occurence of 8 in A is at index 4 ans = [3, 4]

Input 2: 4 5 17 100 111 3

Output 2: -1 -1

Solution of Search for a range in java:–

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  static int firstO(int arr[], int key, int f , int l)
  {
    int res=-1;
    int first=f;
    int last=l;
    
    
    while(first<=last)
      {
        int mid=(first+last)/2;
         if(arr[mid]>key)
         {
            last=mid-1;
         }
        else if(arr[mid]<key)
        {
           first=mid+1;
        }
        else{
          res=mid;
          last=mid-1;
        }
      }
    return res;
  }

  static int lastO(int arr[], int key, int f, int l)
  {
    int res=-1;
    int first=f;
    int last=l;

    while(first<=last)
      {
        int mid=(first+last)/2;
         if(arr[mid]>key)
         {
            last=mid-1;
         }
        else if(arr[mid]<key)
        {
           first=mid+1;
        }
        else{
          res=mid;
          first=mid+1;
        }
      } 
    return res;
  }
	public static void main (String[] args) throws java.lang.Exception
	{
		//your code here
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();

      int arr[] = new int[n];
      for(int i=0;i<n;i++)
        {
          arr[i]=sc.nextInt();
        }
      int b = sc.nextInt();

      int first=0;
      int last=arr.length-1;
      int hello=firstO(arr,b,first,last);
      int demo=lastO(arr,b,first,last);

      System.out.print(hello+" "+demo);
	}
}

Add a Comment

Your email address will not be published. Required fields are marked *