Fill in the missing variables labeled with $x = 1...16 Selection Suppose that yo

Question

Fill in the missing variables labeled with $x = 1...16

Selection Suppose that you have two arrays of integers, A and B. They are both arranged in ascending order. A has length n and B has length m, and n+m> 0. We would like an O(log n + log m) divide and conquer algorithm that can find the element that would be stored at index k if the arrays were merged into a single ordered array For example, suppose A and B are A -[2, 5, 7, 22] B = [7, 8, 9, 14] The element that would be stored at index 5 of the merged array M -[2, 5, 7, 7, 8, 9, 14, 22] is 9, Unfortunately, actually merging A and B would require (n+m) time in the worst case, which is too long. Here is the skeleton of a solution. In 16 places, I have removed an expression and replaced it with $x, for x-1..16 // A and B are each sorted into ascending order, and 0

Explanation / Answer

The statements would be

if(a[i]>b[j])
if(k<=i+j)
return select(a,loa,i-1,b,lob,hib,k);
else
return select(a,loa,hia,b,j+1,hib,k);
else
if(k<=i+j)
return select(a,loa,hia,b,lob,j-1,k);
else
return select(a,i+1,hia,b,lob,hib,k);

This is tested in a c program and it works fine.

Do give a thumbs up and in case there are doubts leave a comment.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.