Question

Let t[1..n] be a sorted array of distinct integers, some of which may be negative. give an algorithm that can find an index i such that 1 i n and t[i] = i

Answer 1

Assuming we need to find i such that
1 ≤ i ≤ n and t[i]=i.

If we need to find only the first occurrence, we can do:

for i:1 to n {
if t[i]=i then return(i)
}

If exhaustive search is required, then put the results (values of i) in an array or a linked list, return the number of values found, and the array (or linked list).