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 su

Question

VMariaS [17]

2 years ago

6

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 su

ch that 1 i n and t[i] = i

Mathematics

1 answer:

lisabon 2012 [21] · Answer 1 · 2022-05-25T02:14:24+03:00

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).