CMI2012-B-03a

Question

Let $A$ be an array of $n$ integers, sorted, so that $A[1] \leq A[2] \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there are indices $k$ and $l$ such that $A[k]+A[l] = x$.

1. Design an $O(n \log n)$ time algorithm for this problem.

Answer 1

a.  Pseudo code for time complexity $O(n\log n)$ :

for(i=1; i<=n; i++)
{
    if (binary_search( x- A[i] ) // O(logn)
    return true;
}
return false;

 

b. Pseudo code for time complexity $O(n)$ :

for( k=1, l=n; k<l ; )
{
    temp =A[k] + A[l];
    if (temp== x)
        return true;
    else if(temp > x)
        l--;
    else
        k++;
}
return false;

 

Comments

@vijaycs

binary_search( x- A[i])

Sir how this line is working in pseudo code (a) ?

---

@Kuljeet Shan,Brother what is binary search first tell?If you answer this then you know how that line binary_search(x-A[i]) is working. 

---

@Kuljeet Shan,Binary search to find the element "x" in logn time. The other part O(n) used for comparison. I hope this serves. 

---

We Can also do heap sort to get T.C. $O(nlogn)$. right??

---

@srestha Could you explain how to apply heapsort and obtain solution to this question?

---

@Kuljeet Shan

binary_search( x - A[i] )

After performing  $x - A[i]$ we get a value when summed with $A[i]$ gives $x$. So if we search that element and find it then $k,l$ indices exists otherwise not.

For example consider the following array $5,10,13,15,20.$ 

If $x=15$ then answer is $A[k]=5$ and $A[l] = 10.$

binary_search($15-5$) =  binary_search($10$).

Hence if we find $10$ solution is over because we already found one value i.e., $A[i]$ and other value is searched value.