(BinSearchi) If the number of items in the list is large, linear search can be a very slow process. Write a program that searches using the following process, called Binary Search. This process assumes that the list of elements in the array are in sorted order, i.e. the l'element in the list. x[0). is the smallest and the last is the largest The template program for Programming Assignment 10 will request a set of non-negative numbers from the user (until a negative value is entered) placing them into a built-in array. It will then sort the numbers in the array so they are in increasing order beginning at index 0. At this point you don't need to understand how this is accomplished; you simply need to know the array will have all its values in numerical order for you to work with the smallest value will be at the smallest index. The program will then prompt the user to enter a value to search for and search the array using a method called binSearch ( arrayName, items, seekItem). This method should return the index at which the element is found or the value-1 if the item is not found in the list. Your search method must use the method outlined below. X Binary Search Process: To find a given element, v, compare it with the element at the middle of the sorted table. If v is smaller, then the element being sought must be in the first half of the table; if v is greater, the it must be in the second half of the table. Then repeat this process on the appropriate half of the array and continue until the item is located or it is determined that the element is not in the list. NOTE this is essentially the process we implemented in Sart2 to estimate the square root of a number. Here is a basic outline of the process you are to implement. Consider the sorted list in array x below. Suppose we with to determine if the value 76 is in the array. As we did with Sqrt2, we will keep track of which part of the list we are presently examining, variable start will represent the index of the first element in the sub-list being presently examined and variable end will represent that index of the last element. Specifically, start will be o to begin with and end will be 10. These two variables will change as we make progress toward locating the desired element. 1 3 6 6 10 13 21 74 76 77 79 index 0 1 2 3 4 5 6 7 10 Step 1: Set start = 0 and end the index of the last element start=0; end=10 Step 2: Find the index of the middle element. middle - 5 Step 3: Check to see if this element is the one we are seeking. The element at index 5 is 13. This is NOT the element we seek. Step 4: If it is then return this index. If not, then adjust start and/or end to enclose to the sub-list in which the sought element must lie. Since this element is smaller than the number being sought, 76, we should continue searching the upper half of the list. So, change start to mid (5 in this case), and go back to the second step. 8 9 Step 5: if start-end, then either we have found the element or it is not present in the list. class BinSearch public static void main(String[] args) tinal int MAX SIZE - 501 Scanner console - new Scanner(System.in) int) item - new int[MAX SITE) / The list of numbers int site- 17 number of values in list int location, seekValue, value: do W request the values and place into array in order entered. System.out.print("Enter a positive number to insert (negative to quit): "); value = console.nextInt() I value > 0) itemt size) - value: site: 2 whilef value > 0) Arrays.sort( item, 0, size): // Sort the values from smallest to largest System.out.println("Element\t\tValue") // Display the current list for(int i 0) System.out.println("Element found at location location: also System.out.println("element not found in list") public static int bin search int[] t, int size, int seekValue // INSERT MISSING CODE HERE! Sample Output: Enter positive number to insert negative to quit 5 Enter a positive number to Insert (negative to quit)6 Enter positive number to insert (negative to quit): 10 Enter positive number to insert negative to quit) + 3 Enter positive number to insert tnegative to quit) 1 2 Enter a positive number to insert thegative to quit): -1 Blement Value O 2 1 3 2 5 2 6 5 10 Entor #value to seekt Nearching index range flow0. high-11. siduess Index Value at index mid=2 L 56, adjusting low to 3. Bearching index range flow, high. mid less indexi - 3 Element found at location 3 Linear and Binary TEMPLATE (20-21) BinSearchi X Compile Undo Cut Copy Paste Find.. Close Source Cod class BinSearch { public static void main(String[] args) { final int MAX_SIZE = 50; Scanner console = new Scanner(System.in): 1/ declaring arrays int[] item = new int[MAX_SIZE]: // The list of numbers int size =0; W number of values in list int location; int seekValue: int value; do { System.out.print("Enter a positive number to insert (negative to quit): "); value = console.nextInt(): if( value >= 0 ) { item[ size 1 = value; size++; > while( value >= 0); Arrays.sort( item, o, size): System.out.println("Element\t\tValue"); I Display the current list for(int i=0; i = 0 ) System.out.println("Element found at location + location): else System.out.println("Element not found in list"): 73 83 1/ Write method binSearch 93 public static int binSearch(int n, int size, { int seekValue) 1-1 indicates element not found int location = -1; int low = 0; int high = size-1; int mid; Wadd missing code return -1