• You can assume that you have access to the function BINARYSEARCH(A[low... high], key) that searches for key in the subarray A[low... high] and returns an index of key if key is present and returns -1 if key is not present. • Quick summary: Brute force is a simple, straightforward, naive, and exhaustive search-based approach. Decrease-and-conquer is a recursive algorithm design tech- nique where a function calls only one instance of itself on a smaller subproblem. 1. [10 points] Given a sorted array of numbers A[1...n], we would like to determine a value x such that both x and -(2x+17) are in the array. If there is, print one such value x, else, print that there is no such value. (i) Design a O(n²) time, (1) extra space algorithm FINDX-NAIVE(A[1...n]) to solve the problem. (ii) Design a O(n log n) time, Ⓒ (n) extra space algorithm FINDX-BETTER(A[1...n]) to solve the problem. (iii) Design a O(n) time, Ⓒ (1) extra space algorithm FINDX-BEST(A[1...n]) to solve the problem.

Fig: 1