The O(n)-time algorithm below searches a sorted array data for two values datale

Question

The O(n)-time algorithm below searches a sorted array data for two values dataleftl and datafright) uch that datalleft] + datalright] t, for a given value of t. Answer the following questions about he algorithm in the case where the array data has two values that add up to t, datalL] and data R here 1SLSRs n. Input: data: sorted array with n integers Input: n: size of data Input: t: integer representing a target value Output: (i,j): indices such that datali + datal]t 1 Algorithm: SumSearch 2 left 1; 3 right = n; 4 while data[left] + data[right]?t do s while dataleft + datafrightt do 6 | | left-left + 1; end s while datalle ft+ datalright]>t do | right = right-1; 10 end 11 end 12 return (left, right); (a) [10 points] Use proof by contradiction to show that if left L and right 2 R and datalle ftl + data[right

Explanation / Answer

a) We have data(left) + data(right) < t the left < L----(1)

   Assuming we have L and R such that
   data(L) + data[R] = t

   For (1) if we say left > L then data[left] > data[L) (array is sorted)
   and we can't have data[left] + data[right] < t

    For (1) if we say left = L then data[left] = data[L) but right > R so
    we can't have data[left] + data[right] < t

b) In lines 5 to 7 if left == L and right = R the loop breaks so the proof is
   trivial.
   If left < L and right > R, then also as we keep on incraesing left the loop
   will break because right > R so we left will reach a index less than L where
   the condition will become wrong. Also as per the part a we have
   left <= L till data[left] + data[right] < t and this is the condition
   for loop iteration also.

c) If right >= R , then till right do not become R or equal to R , L will always
    be less than L or <= L . It is because the sum data[left] + data[right} will never be equal to t and this means lines 4 -11 will always be running. The moment
   left reaches L, the second while loop will take right to R and the outer loop
   will break;
  

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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