Let A be an array of size n of integers, where A[1] ...
(Note that each entry may be a positive or negative integer.)
(a) Give an algorithm that takes O(log n) time to find an i such that A[i] = i, provided such an i exists. If no such i exists, the algorithm returns 0.
(b) Prove that any algorithm to solve this problem using comparisons must take time Ω(log n).