9. [10 points] Given a sorted array A[1...n], we want to count the number of occur- rences of value k in the array. (i) Design a O(n) algorithm (ii) Design a O (log n) algorithm lem. (Hint: Modify binary search and use it.) COUNTFREQUENCY(A[1...n], k) to solve the problem. COUNTFREQUENCY(A[1...n], k) to solve the prob-

Fig: 1