Consider the following problem. Input: An array of sizen>3that consists ofanon-empty decreasing sequence of numbers followed byanon-empty increasing sequence of numbers. Output: The smallest number of array A. For example, givenA=<16, 10, 6, 3, 2, 4, 8, 12, 15, 20>, the output will be 2. Note that for such an array, you can find the smallest number at indexkwith •A[i]>A[i+1] for all1
Consider the following problem.
Input: An array of sizen>3that consists ofanon-empty decreasing sequence of
numbers followed byanon-empty increasing sequence of numbers.
Output: The smallest number of array A.
For example, givenA=<16, 10, 6, 3, 2, 4, 8, 12, 15, 20>, the output will be 2. Note
that for such an array, you can find the smallest number at indexkwith
•A[i]>A[i+1] for all1<i<k
•A[i]<A[i+1] for allk<i<n
Assume index starts from 1.
Designarecursive
number of such an array. [Hint: The idea can be similar to binary search.
(1) Write your algorithm in pseudocode. You will get no point if your algorithm
is non-recursive.
(2) Write a recurrence relation on the running time of your algorithm. Solve it
to giveatight bound.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
