/**
* 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.
*/
public class BinarySearch
/*
* Given a sorted 3D matrix A (sorted in every coordinate in ascending order) and a target key, implement
* the binary search method to find and return the Element with the key that matches the target
* within the range [minX, maxX]x[minY, maxY]x[minZ, maxZ], otherwise return null.
* You must use binary search with proper recursion in the columns and rows of A simultaneously.
*
* @param A is a sorted 3D array, such that
* A[x][y][0].key < ...< A[x][y][n-1].key and A[0][y][z].key < ...< A[n-1][y][z].key
* and A[x][0][z].key < ...< A[x][n-1][z].key, for all x, y, z in {0,...,n-1}.
* @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 minZ is the minimum index in the third coordinate to be searched in A
* @param maxZ is the maximum index in the third 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
tracker.calltracking(minX,maxX,minY,maxY,minZ,maxZ); //Do not modify this method. Otherwise, your answers may not be marked correctly
// TODO: Complete this method
// START YOUR CODE
tracker.calltracking(minX, maxX, minY, maxY,minZ,maxZ); // Do not modify this method. Otherwise, your answers may not be
// marked correctly
// START YOUR CODE
// validating minX, maxX, minY and maxY
if (minX >= 0 && minX <= maxX && maxX < A.length && minY >= 0 && minY <= maxY && maxY < A[minX].length
&& minZ >= 0 && minZ <= maxZ && maxZ < A[minX].length) {
int midX = (minX + maxX) / 2;
int midY = (minY + maxY) / 2;
int midZ = (minZ + maxZ) / 2;
// if value at midX row midY column equals target value, returning Element at
// [midX][midY]
if (A[midX][midY][midZ].key.equals(target)) {
return A[midX][midY][midZ];
}
else if (target.compareTo(A[midX][minY][midZ].key) < 0) {
return search(A, minX, midX - 1, minY, maxY,minZ,midZ-1, target);
}
else if (target.compareTo(A[midX][maxY][midZ].key) > 0) {
return search(A, midX + 1, maxX, minY, maxY,midZ+1,maxZ, target);
}
else if (target.compareTo(A[midX][midY][midZ].key) < 0) {
return search(A, minX, maxY, minY, midY - 1, minZ,maxY,target);
}
else if (target.compareTo(A[midX][midY][midZ].key) > 0) {
return search(A, minX, maxY, midY + 1, maxY,minZ,maxY, target);
}
}
return null; // if not found, or indices are invalid.
// END YOUR CODE
}
}