Build A Binary Search and Maze Solver Using Java Programming Language Assignment Solution

Instructions

Objective

Write a program to build a binary search and maze solverusing Java programming language.

Requirements and Specifications

Part 1: Implement binarySearch method (30 points) In Assignment9.java, you are provided with a method binarySearch(int array[], int lower, int upper, int token). This method takes an integer array, the lower and upper index to search within the array, and the token to search for in the array. It returns the index of the token in the array if it is present, else it returns -1 when the token is not present. You will need to implement this using recursion. Binary search is a technique used to find elements in a sorted array. Since the elements are arranged in ascending order, we can find an element using this technique instead of looking at all the elements of the array as explained below. Given an array of elements of size indexed from 0 to size - 1, 1. Check the value of the middle element. If it is equal to the search token, return the index of the middle element. Here, the search interval is 0 to size - 1. 2. If the value of the middle element is greater than the search token, it implies that the token is present in the 1 st half of the array. Repeat step 1 for the 1 st half of the array. Here, the search interval from index 0 to the index of the middle element - 1. 3. If the value of the middle element is less than the search token, it implies that the token is present in the 2 nd half of the array. Repeat step 1 for the 2 nd half of the array. Here, the search interval is from the index of the middle element + 1 to the index size - 1.. 4. Repeat this process until the search token is found or the search interval is empty.

In Assignment9.java, you are provided with a method mazeSolver(char[][] maze, int row, int col). This method takes a 2D array of characters maze, and the row and col index to enter the maze from. This method returns true if the maze has an escape route or false if it does not have an escape route. In your starter code, you are provided with three constants: PATH, WALL and ESCAPE which represent a path in the maze, a wall in the maze that’s blocking the maze and a path that is a part of the escape route respectively. The below image represents a maze:

Source Code

public class Assignment9 { public static final char PATH = 'P'; public static final char WALL = 'X'; public static final char ESCAPE = 'E'; public static int binarySearch(int array[], int lower, int upper, int token) { // Implement binarySearch() return 0; } public static boolean mazeSolver(char[][] maze, int row, int col) { // Implement mazeSolver() return false; } public static boolean unitTests(){ // Testing binarySearch() int testArray[] = {9, 11, 19, 21, 29, 31, 39, 41}; int actualIndex = binarySearch(testArray, 0, testArray.length - 1, 19); int expectedIndex = 2; if(actualIndex != expectedIndex) { System.out.println("FAILURE: Unexpected output for binarySearch()"); return false; } // Write FIVE more test cases for binarySearch() here. // Testing mazeSolver() char[][] testMaze = new char[][]{{'P', 'X', 'X', 'X'}, {'P', 'P', 'P', 'P'}, {'X', 'P', 'X', 'P'}, {'X', 'P', 'P', 'P'}}; boolean actualOutput = mazeSolver(testMaze, 0, 0); boolean expectedOutput = true; if(actualOutput != expectedOutput) { System.out.println("FAILURE: Unexpected output for mazeSolver()"); return false; } // Write FIVE more test cases for mazeSolver() here. return true; } public static void main(String args[]) { if(unitTests()){ System.out.println("All unit tests passed."); } else { System.out.println("ERROR: Failed test."); } } }