CS计算机代考程序代写 /**

/**
* Skeleton code for Binary Search.
* You are required to implement the binary search method using proper recursion.
*
* The given code is provided to assist you to complete the required tasks. But the
* given code is often incomplete. You have to read and understand the given code
* carefully, before you can apply the code properly. You might need to implement
* additional procedures, such as error checking and handling, in order to apply the
* code properly.
*/
package Midterm.Q1;

public class BinarySearch> {

/*
* Given a sorted 2D matrix A (sorted in all columns and rows) and a target key, implement
* the search method to find and return the Element with the key that matches the target
* within the range [minX, maxX]x[minY, maxY], otherwise return null.
* You must use binary search with proper recursion in the columns and rows of A simultaneously.
*
* @param A is a sorted 2d array, such that A[i][0].key < ...< A[i][n-1].key and A[0][j].key < ...< A[n-1][j].key for all i, j * @param minX is the minimum index in the first coordinate to be searched in A * @param maxX is the maximum index in the first coordinate to be searched in A * @param minY is the minimum index in the second coordinate to be searched in A * @param maxY is the maximum index in the second coordinate to be searched in A * @param target is the target key * @return the object with the matched key if exist, otherwise return null. */ public Element search(Element[][] A, int minX, int maxX, int minY, int maxY, T target) {
tracker.calltracking(minX, maxX, minY, maxY); //Do not modify this method. Otherwise, your answers may not be marked correctly
// TODO: Complete this method
// START YOUR CODE

int x, y;
x = (minX + maxX) / 2;
y = (minY + maxY) / 2;
Element center = A[x][y];

if (center.key.equals(target)) return center;

if (maxX == minX && maxY == minY) return null;
else {
if (maxX != minX && maxY != minY) {
if (target.compareTo(center.key) > 0) {
Element one = search(A, minX, x, y + 1, maxY, target);//tr
Element two = search(A, x + 1, maxX, minY, y, target);//bl
Element three = search(A, x + 1, maxX, y + 1, maxY, target);//br
return one == null ? two == null ? three : two : one;
} else {
Element one = search(A, minX, x, minY, y, target);//tl
Element two = search(A, minX, x, y + 1, maxY, target);//tr
Element three = search(A, x + 1, maxX, minY, y, target);//bl
return one == null ? two == null ? three : two : one;
}
}
if (maxX == minX) {
Element one = search(A, minX, minX, y + 1, maxY, target);//tr
Element two = search(A, minX, minX, minY, y, target);//bl
return one == null? two: one;
}
Element one = search(A, minX, x, minY, minY, target);//tl
Element two = search(A, x + 1, maxX, minY, minY, target);//tr
return one == null? two: one;
}
// return null;
// END YOUR CODE
}
}
//另解
//if((target.compareTo(A[maxX][maxY].key)>0) || (target.compareTo(A[minX][minY].key)<0)){ // return null; // } // int midX = (minX + maxX)/2; // int midY = (minY + maxY)/2; //// check row_number X is fixed or not // if((midX == minX || midX == maxX) && A[midX][maxY].key.compareTo(target)>=0){
// // check column_number Y is fixed or not
// if((midY == minY || midY == maxY)){
// if(A[midX][midY].key.equals(target)){
// return A[midX][midY];
// }else if(A[midX][midY+1].key.equals(target)){
// return A[midX][midY+1];
// }else {
// return null;
// }
// }
// // given fixed X to fix Y
// else if(A[midX][midY].key.compareTo(target)<0){ // return search(A,midX,midX, midY+1 ,maxY,target); // // }else { // return search(A,midX,midX, minY ,midY,target); // } // } //// to fix Y // if(A[midX][maxY].key.compareTo(target)<0){ // return search(A,midX+1,maxX, minY ,maxY,target); // }else { // return search(A,minX,midX, minY ,maxY,target); // } // if((maxX-minX)==1&&(maxY-minY)==1){ // if(A[minX][minY].key==target){ // return A[minX][minY]; // }else if(A[minX][maxY].key==target){ // return A[minX][maxY]; // }else if(A[maxX][minY].key==target){ // return A[maxX][minY]; // }else if(A[maxX][maxY].key==target){ // return A[maxX][maxY]; // }else{ // return null; // } // } // A[midX][midY]>target
// Element leftcorner=searchhepler(A, minX,midX,minY,midY, target);
// Element left= searchhepler(A,minX,midX,midY,maxY, target);
// Element top=searchhepler(A,midX,maxX,minY,midY, target);
// Element rightcorner = searchhepler(A,midX,maxX,midY,maxY,target);
// Element bottom = searchhepler(A,minX,midX,midY,maxY,target);
// Element right = searchhepler(A,midX,maxX,midY,maxY,target);

// T source = A[midX][midY].key;
// int cmp = source.compareTo(target);
// System.out.println(“cmp:”+cmp);
//
// if (cmp == 0) {
// System.out.println(“yes”);
// return A[midX][midY];
// }
// else if (cmp > 0) {
// if(searchhepler(A, minX,midX,minY,midY, target)!=null){
// System.out.println(“test1”);
// res = searchhepler(A, minX,midX,minY,midY, target);
// }else if(searchhepler(A, minX,midX,minY,midY, target)!=null){
// res = searchhepler(A, minX,midX,minY,midY, target);
// }else if(searchhepler(A,midX,maxX,minY,midY, target)!=null) {
// res = searchhepler(A,midX,maxX,minY,midY, target);
// }else{
// return null;
// }
// if(res!=null){
// return res;
// }else{
// return null;
// }
// }
// // A[midX][midY]