Fundamental Algorithm

Identity Element in an Array

Let A be an array with n distinct integer elements in sorted order. Consider the following algorithm IDFIND(A,j, k) that finds an i E {jk such that AM-i, or returns FALSE if no such element i exists. I DFIND(A, j, k) 2 if j>k return FALSE Set i := 4 if Ali]-. return f AE.. . return loFIND(. 6 return IDFINDIA....) (a) (3 points) Fill in the blanks (denoted.. to complete the above algorithm (b) (5 points) Prove correctness and analyze the running time of the algorithm Notice the emphasis on Prove, you can't just say "my algorithm works because it works") (c) (2 points) Does the algorithm work if the elements of A are not distinct? Why or why not