Search For A Range in java

Search For A Range in java

Problem Desrciption :

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.*;
 
class Main {
    public static int[] searchRange(final int[] A, int B) {
       int lowIndex = searchLow(A, B,0, A.length - 1);
      if(lowIndex == -1)
      {
        return new int[]{-1, -1};
      }
      int highIndex =  searchHigh(A, B,0, A.length - 1);
      return new int[]{lowIndex, highIndex};
    }
 
    public static int searchLow(int[] A, int B, int low, int high) {
      if(low > high)
        return -1;
 
      int mid = (low+high)/2;
      if(A[low] == B)
        return low;
 
      else if(A[mid] >= B)
      {
        return searchLow(A, B, low+1, mid);
      }
      else
      {
         return searchLow(A, B, mid+1, high);
      }
    }
 
    public static int searchHigh(int[] A, int B, int low, int high) {
     if(low > high)
        return -1;
 
      int mid = (low+high)/2;
      if(A[high] == B)
        return high;
 
      else if(A[mid] > B)
      {
        return searchHigh(A, B, low, mid-1 );
      }
      else
      {
         return searchHigh(A, B, mid, high-1);
      }
    }
 
  public static void main (String[] args)
	{
    Scanner sc = new Scanner(System.in);
 
    int N = sc.nextInt();
    int[] A = new int[N];
    for(int i=0;i<N;i++){
        A[i] = sc.nextInt();
	}
	int B = sc.nextInt();
	int[] ans = searchRange(A,B);
    System.out.println(ans[0] + " " + ans[1]);
 
	}
}
 

Add a Comment

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