CS 344 Sections 1,2,3 Fall 2018 Homework 4. Due Tuesday, November 13, 11:55pm 80 points total plus extra credit Problem 1: Random Binary Search (20 points total) 1 Consider the Following Problem: . Input: a sorted array A of length n, and a target numberk Owsgpet: indes isuch that Al- or no solion f e Previously, we showed that binary search solves this problem in O(log(n) time by repeatedly looking at the middle and recursing to one side. Let's say that instead of picking the middle element, we picked a random element in the array. Here is the pseudocode. Algorithm: RandomBinarySearch(A,k,left,right) in the initial call, left 0 and right n-l 1. If left > right return "no solution" 2. iRand(left....right) 3. If Ali] k return i 4. If AH >k return RandomBinarySearch(A,k,left, i-1) 5. IfAlilck . RandomBinarySearch(A,k,i+1,right) In this question, we will figure out the expected running time of this RandomBinarySearch. Note that all the work done by the algorithm consists of comparing some Alt] to k (and then recursing and comparing some other Ali to k). In particular, each Ali] is compared to k either 0 or 1 times. The expected running time is thus the expected number of comparisons made by the algorithm. CS 344 Sections 1,2,3 Fall 2018 Homework 4. Due Tuesday, November 13, 11:55pm 80 points total plus extra credit Problem 1: Random Binary Search (20 points total) 1 Consider the Following Problem: . Input: a sorted array A of length n, and a target numberk Owsgpet: indes isuch that Al- or no solion f e Previously, we showed that binary search solves this problem in O(log(n) time by repeatedly looking at the middle and recursing to one side. Let's say that instead of picking the middle element, we picked a random element in the array. Here is the pseudocode. Algorithm: RandomBinarySearch(A,k,left,right) in the initial call, left 0 and right n-l 1. If left > right return "no solution" 2. iRand(left....right) 3. If Ali] k return i 4. If AH >k return RandomBinarySearch(A,k,left, i-1) 5. IfAlilck . RandomBinarySearch(A,k,i+1,right) In this question, we will figure out the expected running time of this RandomBinarySearch. Note that all the work done by the algorithm consists of comparing some Alt] to k (and then recursing and comparing some other Ali to k). In particular, each Ali] is compared to k either 0 or 1 times. The expected running time is thus the expected number of comparisons made by the algorithm