Part 2: Binarv Search When you search for a page in a book, have you ever thought how you do it? Everyone (I hope) when searching for a page performs a form of Binary Search. What this means is that say I give you a page to find, say 242, in a book of unknown page length (the paper is weird material). You'd probably start by opening it to the middle. You'd check the page. Let's say you opened it to page 500 Where wvould you search next? Well, ifyou were logical, you wouldn't even bother searching the right half of the book. You'd repeat the same logic on the left side of the book until you hit the goal page. Since you now are only looking at the left side, you open to the middle page and find that it is 250. Still not 242 but you can narrow your search and only look at the left side of this section (pages 0 -> 250). The next page you open is 125. Then you open to 187. Then 218. Getting closer. You know the page must be between 218 and 250. I won't do the rest of the page flipping for you but by repeating this same idea (check the middle, repeat the function to the left or right), you can quickly find the goal page much faster than flipping from page 1 all the way to the goal page, checking every page along the way. That in essence is binary search: a more efficient way to search an ordered list for an item Oh yeah, and this algorithm is recursive (you can implement it with loops but good luck. It's simpler with a recursive function Write the Base case Write the Recursive Hvpothesis Write the Recursive Step Write the code for this function in Java: What is the running time of this algorithm (estimate it)