Question

Given a sorted array of integer, A, with possible duplicate elements. Implement an efficient (sublinear running time complexity) function in Java to find in A, the numbers of occurrences of the input value k. For example, in an array A = {-1, 2, 3, 5, 6, 6, 6, 9, 10} and k = 6, your program should return 3.

Answer 1

Answer:

The java program is as follows.

import java.util.*;

import java.lang.*;

public class SearchProgram

{

   // sorted array may or may not containing duplicate elements

   static int A[] = {-1, 2, 3, 5, 6, 6, 6, 9, 10};

   

   // variable to keep track of number of occurrences, declared and initialized to 0

   static int times=0;

   

// variable to hold value to be searched in the array

   static int key;

   static int search(int[] art, int n)

   {

       // enhanced for loop used to find how many times n occurs in array, arr

       for(int j:arr)

       {

           if(n == j)

               times = times+1;

       }

       

       return times;

   }

   

   public static void main(String[] args)

   {

       // scanner object to allow user input

       Scanner sc = new Scanner(System.in);

       

       // user prompted to enter key to be searched

       System.out.print("Enter the element to be searched: ");

       key = sc.nextInt();

       

       // message displayed to the user on how many times the element is present in the array

       System.out.println("The element " + key + " is present " + search(A, key) + " times in the array.");

   

   }

}

OUTPUT

Enter the element to be searched: 3

The element 3 is present 1 times in the array.

Explanation:

The steps of program execution are shown below.

1. An integer array, A, is declared and initialized.

2. An integer variable, times, is declared and initialized to 0.

3. A method, search(), is created which takes 2 parameters, array A and user entered value for the element to be searched in A.

4. The search() method has return type of integer and returns the value of variable, times.

5. Inside the search() method, an enhanced for loop is used to compute the value of the variable, times.

6. In the main() method, user is prompted to enter the value of key.

7. The search() is called and value of the variable, times, displayed to the user.

8. All the methods and variables are declared as static.