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

Question

Mathematics

Jacquelyn Monroe

8 December, 10:06

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

+1

Answers (1)

Know the Answer?

Karissa Campos · 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).