3. Let T₁……. be a sorted array of distinct integers, some of which may be negative. I...n (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₁……. be a sorted array of distinct integers, some of which may be negative. I...n (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
question 3
Transcribed Image Text:3. Let T₁……. be a sorted array of distinct integers, some of which may be negative.
I...n
(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 with 2 images
