Remarks: In all the algorithms, always explain precisely your solution or prove if required.

You Always Must analyze the running time of any algorithm. The time complexity should

be as small as possible. A correct algorithm with large complexity, may not get full credit.

Don't write programs for your solutions.

Question $2$: Let $A$ be a sorted array that has negative or positive integers. For example

Give an algorithm that finds out if there is a positive integers

$i$ so that $A[i]=i$