Do the binary search for the method if an array is given and there might be repeated values. It is a 2D array.

For this assignment, you are to write a count method to search for a given number in a two dimensional array and return the number of times that the number appeared in the array. The array is sorted in each column but the rows are not necessarily sorted. For example, given the following array and the query element 20, your method should return 5 which is the number of times that 20 appeared in the array. = 15 8 10 6 18 10 20 15 20 15 25 20 20 20 32 25 The most straightforward (but inefficient) solution is to do a linear search and traverse the entire 2D array and add up the number of times that the element occurs in the array. The linear solution will be of O(mn) where n is the number of rows and m is the number of columns. A smarter solution takes advantage of the fact that the columns are sorted and uses a binary search to avoid unnecessary comparisons. Your method should implement this smarter solution and must be more efficient than the linear search. What you need to do: Download the COUNT.zip file posted on Blackboard and extract it. The folder contains four files: 1. CountOccurence.java: This class has a method count which counts the number of occurrences of a given number in the array. This is the method that you need to implement. 2. array.txt: This file contains a two dimensional array of numbers with 1000 rows and 5000 columns (for a total of 5 million numbers). This is the array we will use to test your program. The first line consists of two numbers: the number of rows and the number of columns. The array starts from the second line. This is to make testing different sized arrays easier for you without needing to write a parsing method that converts strings to integers. 3. query.txt: This file contains a set of query numbers (one number per line) and for each number we wish to count the number of times that it occurs in the arrayif it occurs. 4. TestCount.java: This class has a main method which reads the data from files array.txt and query.txt and calls the count method to count the number of times that each number in the query.txt occurs in the array. 5. Expected_output.txt: This is the expected output you should get when running the TestCount.java program. Your job for this assignment is to implement the count method in file countOccurence.java: public int count(int arr[][], int query) This method gets a 2D array and a query as arguments and returns the number of times that the query occurs in the array. The 2D array is sorted by columns but not by rows. Your method must take advantage of the fact that each column is sorted and use binary search to avoid some unnecessary comparisons. You may use any helper methods you want but make sure to include comments to clarify what each method does. Once you write the count method run the TestCount.java file to test your method on the large 2D array in the array.txt file for each query element in the query.txt. Please note that you need to copy the array.txt and the query.txt files in your main project folder and then run the TestCount.java file. After running the program a file count_result.txt will be generated which contains the result of your method. Compare your file with the expected_output.txt to see if they are the same.

Count_Occurence.java

/**

* A class to count the number of occurrences of an element in a 2-D array

* @author elhams

*

*/

public class CountOccurrence {

/**

* This method counts the number of occurrences of query in the array.

* You have to implement this method. You may use any helper method you want.

* @param query

* @return

*/

public static int count(int[][]array, int query){

}

}

CountOccurenceJunitest.java

import java.io.BufferedWriter;

import java.io.File;

import java.io.FileNotFoundException;

import java.io.FileWriter;

import java.util.Scanner;

import org.junit.Ignore;

import org.junit.Test;

public class CountOccurrenceJUnit {

@Test

public void test_count_4_return_3() {

int arr[][] = new int[][] {

{1, 1, 1},

{2, 2, 2},

{4, 4, 4},

{5, 5, 5}

};

assert(CountOccurrence.count(arr, 4) == 3);

}

@Test

public void test_count_corners_return_8() {

int arr[][] = new int[][] {

{1, 0, 1},

{1, 2, 1},

{1, 4, 1},

{1, 5, 1}

};

assert(CountOccurrence.count(arr, 1) == 8);

}

@Test

public void test_count_2_return_2() {

int arr[][] = new int[][] {

{1, 2, 3, 4, 5, 6},

{2, 3, 4, 5, 6, 7},

{3, 4, 5, 6, 7, 8},

{4, 5, 6, 7, 8, 9}

};

assert(CountOccurrence.count(arr, 2) == 2);

}

@Test

public void test_full_array_return_80() {

int arr[][] = new int[][] {

{5, 5, 5, 5, 5, 5, 5, 5},

{5, 5, 5, 5, 5, 5, 5, 5},

{5, 5, 5, 5, 5, 5, 5, 5},

{5, 5, 5, 5, 5, 5, 5, 5},

{5, 5, 5, 5, 5, 5, 5, 5},

{5, 5, 5, 5, 5, 5, 5, 5},

{5, 5, 5, 5, 5, 5, 5, 5},

{5, 5, 5, 5, 5, 5, 5, 5},

{5, 5, 5, 5, 5, 5, 5, 5},

{5, 5, 5, 5, 5, 5, 5, 5},

};

assert(CountOccurrence.count(arr, 5) == 80);

}

@Test

public void test_count_non_existant_return_zero() {

int arr[][] = new int[][] {

{1, 2, 3, 4, 5, 6},

{2, 3, 4, 5, 6, 7},

{3, 4, 5, 6, 7, 8},

{4, 5, 6, 7, 8, 9}

};

assert(CountOccurrence.count(arr, 10) == 0);

}

@Ignore

@Test

public void test_file_query() {

try{

//Reading data from array.txt and load it into two dimensional array data

Scanner fileIn = new Scanner(new File("array.txt"));

//The first line contains the number of rows and columns

int row = fileIn.nextInt();

int col = fileIn.nextInt();

int data[][] = new int[row][col];

System.out.println("Reading in data...");

for(int r = 0; r < row; r++){

fileIn.nextLine();

for(int c = 0; c < col; c++){

data[r][c] = fileIn.nextInt();

}

}

//Reading the query.txt file and testing the count method for each number in the query.txt

fileIn = new Scanner(new File("query.txt"));

System.out.println("Starting query...");

//Creating an output file to store the count result

File f= new File ("count_result.txt");

BufferedWriter output = new BufferedWriter(new FileWriter(f));

//marking the start and end times to measure the running time of the algorithm

long start = System.nanoTime();

//Calling the count method for each line in the query.txt

while(fileIn.hasNextLine()){

int query = fileIn.nextInt();

output.write("" + CountOccurrence.count(data,query));

output.write(" ");

fileIn.nextLine();

}

long end = System.nanoTime();

System.out.println("Querying has ended...");

System.out.println((end - start)/1000000 + "ms");

fileIn.close();

output.close();

System.out.println("Comparing results");

compareFiles();

} catch(Exception e){

e.printStackTrace();

}

}

private static void compareFiles() throws FileNotFoundException{

Scanner expected = new Scanner(new File("expected_output.txt"));

Scanner result = new Scanner(new File("count_result.txt"));

int incorrect = 0;

while(expected.hasNextLine() && result.hasNextLine()){

String expectedLine = expected.nextLine();

String resultLine = result.nextLine();

if(!expectedLine.equals(resultLine)){

System.out.println("Expected: " + expectedLine);

System.out.println("\tResult: " + resultLine);

incorrect+=1;

}

}

System.out.println("Incorrect Results: " + incorrect);

expected.close();

result.close();

if(incorrect != 0) {

throw new AssertionError("You have incorrect solutions");

}

}

}

I did not include arraytxt, querytxt and expectedoutput.txt because they are too big but you really need those to do the problem just provide me with an email where I can attach and send it.