3. Let T₁...n be a sorted array of distinct integers, some of which may be negative. = (a) Design a (log n) Divide and Conquer algorithm that finds an index i such that 1 ≤ i ≤n and Ti i or correctly reports that such an index does not exist. Prove that your algorithm runs in O(log n) in all cases. (b) Suppose that we also know that T₁ computes the index i such that Ti exist. = 0. Design an even faster algorithm that either i or correctly reports that such an index does not
3. Let T₁...n be a sorted array of distinct integers, some of which may be negative. = (a) Design a (log n) Divide and Conquer algorithm that finds an index i such that 1 ≤ i ≤n and Ti i or correctly reports that such an index does not exist. Prove that your algorithm runs in O(log n) in all cases. (b) Suppose that we also know that T₁ computes the index i such that Ti exist. = 0. Design an even faster algorithm that either i or correctly reports that such an index does not
Related questions
Question
in the 3b, is T[1] > 0
Transcribed Image Text:3. Let T₁...n be a sorted array of distinct integers, some of which may be negative.
=
(a) Design a (log n) Divide and Conquer algorithm that finds an index i such that 1 ≤ i ≤n
and Ti i or correctly reports that such an index does not exist. Prove that your
algorithm runs in O(log n) in all cases.
(b) Suppose that we also know that T₁
computes the index i such that Ti
exist.
=
0. Design an even faster algorithm that either
i or correctly reports that such an index does not
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
