Search for question
Question

Numéro 5. (19 pts) Let be an array t, indexed by 0 to n-1. We want to find an index i such as

t[k] ≤t[i] for 0 ≤ k < i and t[k] >t[i] for i+1≤k

In other words, find an index i such that all the elements to the left of t[i] are all smaller than or

equal to t[i] and all elements on the right of t[i] are all larger than t[i]. Note that such an index may

not exist, or there may be several indices that satisfy the condition. Here are a few examples:

table

[3, 6, 1,5]

[4,0,8,-1,6, 15, 22, 19]

[11, 8, 1, 4, 17, 26, 52, 25, 19, 55, 65, 60, 70, 100, 99]

possible clues

none

5

4,9,12

(a) (10 points) Find the algorithm linear in the worst case. Your algorithm doesn't have to

give the highest value of the index found, but one of them, or -1 if no such index exists.

Give the pseudo-code of your algorithm.

(b) (4 points) Keep track of your algorithm with a few tables.

(c) (5 points) Perform an asymptotic analysis of your algorithm.

Response :

Fig: 1