Consider the following list of integers: In this example, the root will be (array position 5) and the value of 6. Keep in mind that positions in the array begin at 0. If the search term were entered to be 2, then the midpoint would be selected which we would determine with the following formula: midpoint = length of array /2 Since the length is 11, the midpoint is position 5. We would then compare the search term 3 to the value in position 5 and since 3 < 6 the search will continue on the left side of the tree structure. We would repeat the process. With the following formula: newbranch = current position / 2 The new length of the array is the left side of the tree up to the root which is 5. This new formula would yield position 2 which is the value 3. Since our search value is 2, it is less than the new branch of the tree meaning that our search value must be on the left of this branch. We repeat this process one more time: newbranch = = current position / 2 The current position is 2 so the new index position will be 1 which contains the value of 2. Our search term is 2 and the value in the new position is also 2 meaning that we have found the value we were looking for. In this case our algorithm required 3 iterations to find the search term. The following code details the algorithm for the preceding example. You can use this code to further understand binary tree implementations and leverage some of the techniques that are supported within Jeliot, however, you cannot use this code as the basis for your assignment. // // Example of an array based implementation of a binary search developed in the Jeliot tool // import Prog1Tools.IOTools; import java.util.*; public class binarySearchTree public static void main (String] args) { int iterations; // This variable counts the number of iterations of search that occur int index; // This variable identifies the node of the tree currently being searched int prev; // This variable will be used to keep track of the 'range' of the branch int searchValue; // This variable will contain the value we are searching for // // In this example we are using an array implementation of a binary tree and the array // is being pre-populated with the integers in the tree in the correct sequence. // in your assignment you must populate your binary tree by accepting values // from the user and populating a structure in the proper sequence using either // an array or linked list implementation // int bTree[] = {1,2,3,4,6,7,8,9,10,12,13,14,15,16,17,18,19,20,21,23,24,25,26,27,2 8, 29,30,33,34,35,36,37,38,39,40 }; %3D // // Using Jeliot, you can use the System.out.printin method to output information // to the console. // System.out.printin("Enter an integer between 1 and 40 to search for:"); // // Using Jeliot, you must use the scanner class to get input from the user as // illustrated below. // Scanner in = new Scanner(System.in); in.nextInt(); searchValue = iterations=1; // // In this section we set the initial midpoint of the array which is the root value // index=bTree.length /2; prev=bTree.length; // // Here we call the binary search method which is designed to recursively // search until the proper value has been found // binarySearch(bTree, index, prev, searchValue, iterations); } public static void binarySearch(int[] bTree, int index, int prev, int searchValue, int iterations) { // // If our search value is smaller then the current position then // we need to search the left branch of the tree. The index value // indicates the current node that is being compared with the search value // the prev value is used to help identify the width of the current branch /l so that we can identify the next branch to follow down. // if (bTreeſindex] < searchValue) { index = (prev-index)/2+index; iterations++; binarySearch(bTree, index, prev, searchValue, iterations); } // // If our search value is larger than the current position then // we need to search the right branch of the tree. Note that in each // iteration of the search we recursively call binarySearch which searches // the next level down in the tree. // else if (bTree[index] > searchValue ) { prev = index; index = index / 2; iterations++; binarySearch(bTree, index, prev, searchValue, iterations); } // // When the search value is found, print the number of iterations the search // took to the console and exit the binarySearch method // else { System.out.printIn("Found search value in:"+iterations+" iterations"); return; } } } In the preceding example, the tree values were created in sequence meaning that the array was populated with values in order. Your algorithm must be able to accommodate values entered in any sequence which means that you must be able to adjust the structure of the tree as the root value and other values change. In the example above, we have an array that forms the basis of our binary search tree. We determine the root by looking midway through the array. The example above has an advantage in that the array is already in sorted order. In your algorithm you will not have that advantage. When you have completed your algorithm and your Asymptotic analysis of your algorithm please run it several times within Jeliot and observe the results. Use the following values for both the contents of the binary search tree and the search value: Integers to add to binary search tree: 10, 5, 12, 3, 1, 13, 7, 2, 4, 14, 9, 8, 6, 11 Search value: 9 Is the time (expressed in the number of iterations required to complete a search) consistent with your Asymptotic analysis in worst case (Big O)? As part of your assignment, you must submit both a description of the assignment and how your algorithm works including an Asymptotic analysis of your algorithm. Your analysis must include the efficiency of your algorithm expressed in Big Oh notation. The scope of your asymptotic analysis should only include the binary search portion of your assignment. Further, as part of your assignment, you must include the code of your algorithm. All of these elements of this assignment must be completed and posted to the assignment for Unit 4 by the end of the week for unit 4. Finally, you must include a screen shot or other capture of the output of you binary search tree that indicates the number of iterations that were required to find the search value.