edited by
334 views
0 votes
0 votes
Let $A$ be a sorted array of $n$ positive integers, such that $A[1] \leq A[2] \leq \dots \leq A[n]$. Given an integer $x$ as input, the goal is to find two array indices $k$ and $l$ such that $A[k]+A[l] =x$, if such indices exist; otherwise, the goal is to report 'Failure". Design an algorithm for this problem, that works in $O(n)$ time.
edited by

1 Answer

0 votes
0 votes

findPair(int x, int[] A){
        int k = 0, l = A.length - 1;
        while(k < l){
            if(A[k] + A[l] == x) return "Success";
            else if(A[k] + A[l] > x) l--;
            else k++;
        }
        return "Failure";
    }

Related questions