Exercise 2: Binary Search Binary search is an efficient algorithm for finding the location of a value in a sorted array. Given a key value to be found, the algorithm first examines the middle element of the array. Say the middle element's value is less than the key value, and assuming the array is sorted in ascending order, then the key can only be in the upper part of the array. The process is repeated on the upper part of the array, examining its middle element and comparing to the key value to be found. At each step, the length of the sub-array being examined shrinks by (approximately) a factor of 2, until the key is found (it is the middle element of the sub-array being examined) or the sub-array size has shrunk to zero (in which case the key value is not in the array). Example 1: Find key 21 Step #1: compare middle element to key-key > mid | 2 | 3 | 6 | 9 |10| 19| 20121| 32 20 21 32 39 10 19 2021 32 6 9 19 | Step #2 : compare middle element to key key , mid | Step #3: compare middle element to key: key-mid 2 Example 2: Find key 9 Step # 1: compare middle element to key: key mid 2 3 6 | 9 | 10-9 , 20 | 2 32 Step #3 : compare middle element to key keys-mid | 2 | 3 | 6-10 | 19 | 20 | 21 | 32 Task: Write an implementation of Binary Search in Java that takes an array of integers (already sorted in ascending order) and a key value to be found and returns the index of the key value in the array. If the key is not found then return -1 public static int findIndex0f(int key, int[] a) { } It is possible to implement this method using 8 Java statements. Q. What is the average time complexity of the Binary Search algorithm? If the input array were not pre-sorted then we could not use Binary Search. What time complexity would this unsorted search problem have