Don't use binary search, and seriously consider the case when it returns either -1 or 1 arbitrarily if both of A[i] and A[j] are -1.

4. (5 points) Given a string A[1n], where A[i]{1,1} for 1in. The only way to access the elements in A is by an operation test (i,j), which - returns 1 , if both A[i] and A[j] are 1 . - returns 1, if exactly one of A[i] or A[j] is 1 . - returns either -1 or 1 arbitrarily if both of A[i] and A[j] are 1. Assuming that i=1nA[i]1, design an algorithm that finds an index 1kn such that A[k]=1. Use as few test (i,j) operations as possible. Give a tight bound on the number of operations in asymptotic notations as a function of n