find indices of sorted array such that a[i]+a[j]=x

Question

This is an interview question: given an integer x and a sorted array a[] of N distinct integers, design a linear-time algorithm to determine if there exists two distinct indices i and j such that a[i] + a[j] == x. No auxiliary storage is allowed. I have implemented this in Java. but my current run time is O(nlogn) because I do a binarySearch on each iteration. so it is not strictly linear. I am wondering if there exists a linear time solution for this problem. If so, some pointers on it could be helpful.

Thanks.

public class SumArrayIndex {

    public static void main(String[] args){

        int[] arr={1,2,3,4,5,6,7,8,9,10};
        sumSortedArray(arr, 4);
        System.out.println();
        sumSortedArray(arr, 19);
        System.out.println();
        sumSortedArray(arr, 100);

    }

    public static void sumSortedArray(int[] arr, int sum){
        for (int i=0;i<arr.length;i++){
            int temp=Arrays.binarySearch(arr, sum-arr[i]);
            if (temp>0 && temp!=i){
                System.out.printf("The two indices are %s and %s%n ",i,temp);
                return;
            }
        }
        System.out.printf("The sum:%s cannot be formed with given array:%s",sum,Arrays.toString(arr));
    }
}

Answer 1

As suggested by @leif in the comment, start from the begin and end of array, move the begin index or end index if the sum is greater or smaller. you should find a begin and end index such that their values equal sum. if not, you there exists no such indices. something on this line below. I have not tested this code and assuming positive integers

The code below is self explanatory:

public static void sumSortedArray2(int[] arr, int sum){
        boolean found=false;
        int max=arr.length-1;
        int min=0;
        while (min<max){
            if(arr[min]+arr[max]<sum)
                min++;
          else if (arr[min]+arr[max]>sum)
                max--;
          else {
              found =true;
              break;
          }
    }
    if (found){
        System.out.printf("The two indices are %s and %s%n ",min,max);
    }
    else {
        System.out.printf("The sum:%s cannot be formed with given array:%s",sum,Arrays.toString(arr));
    }
}

Answer 2

You can modify your algorithm to be linear time, with these observations:

1. Without losing the generality, you can say that i and j are such that arr[i]<arr[j]. Proof: if that is not so, you can swap i and j.
2. Considering that you started the search at the beginning, when you search for sum-arr[i], you can always search to the right of index i; if sum-arr[i] < arr[i], you know that there is no answer, because j would be to the left of i
3. If your previous search for sum-arr[i] has ended at index k without yielding a result, your next search can go between indexes i and k.
4. You do not need to search for sum-arr[i] using a binary search: you can do a linear search from the back, and keep the point k where arr[k] < sum-arr[i] as your next starting point.

This lets you build an algorithm that examines each item exactly once.