Question

An increasing-order integer array may contain duplicate elements. Write a Java method that does a binary search through the array for finding a specific target and return an array of two integer indices that specifies the close interval of indices at which the target is found or null if the target is not present. Use this test driver to test

public class MultBS

{

int [] multBinarySearch(int [] x, int target)

{

// your codes go here

}

public static void main(String [] args)

{ int [] x = new int[]{2,3,3,4,4,4,5,6,7,7,7};

int [] range = multBinarySearch(x, 3);

System.out.println("Target was found from position " + range[0] + " to " + range[1]);

}

}

test your program to make sure you see

the printout is

"Target was found from position 1 to 2"

Answer 1

import java.io.*;
public class MultBS
{
    private static int first_BS(int [] x, int target, int l, int r)
    {
        if(l>r)
            return -1;

        int mid = (r-l)/2+l;

        if(x[mid] == target && (mid==0 || x[mid-1] != target))
            return mid;
        else if(x[mid] == target)
            return first_BS(x, target, l, mid-1);
        else if(x[mid]>target)
            return first_BS(x, target, l, mid-1);
        else
            return first_BS(x, target, mid+1, r);
    }

    private static int last_BS(int [] x, int target, int l, int r)
    {
        if(l>r)
            return -1;

        int mid = (r-l)/2+l;

        if(x[mid] == target && (mid==x.length-1 || x[mid+1] != target))
            return mid;
        else if(x[mid] == target)
            return last_BS(x, target, mid+1, r);
        else if(x[mid]>target)
            return last_BS(x, target, l, mid-1);
        else
            return last_BS(x, target, mid+1, r);
    }
    private static int [] multBinarySearch(int [] x, int target)
    {
        int[] ans={-1,-1}; // -1 represents null
        ans[0] = first_BS(x, target, 0, x.length-1);
        ans[1] = last_BS(x, target, 0, x.length-1);
        return ans;
    }

    public static void main(String [] args)
    {
        int [] x = new int[]{2,3,3,4,4,4,5,6,7,7,7};
        int [] range = multBinarySearch(x, 3);
        System.out.println("Target was found from position " + range[0] + " to " + range[1]);
    }

}