As it said in the topic, I have to check if there is a number that is the sum of two other numbers in a sorted array.

In first part of the question (for a unsorted array) I wrote a solution, just doing 3 loops and checking all the combinations.

Now, I can't understand how to build the most efficient algorithm to do the same, but with a sorted array.

Numbers are of type `int`

(negative or positive) and any number can appear more then once.

Can somebody give a clue about that logic problem ?

# Best How To :

Here I am doing it using C:

An array A[] of n numbers and another number x, determines whether or not there exist two elements in S whose sum is exactly x.

**METHOD 1 (Use Sorting)**

**Algorithm:**

hasArrayTwoCandidates (A[], ar_size, sum) 1) Sort the array in non-decreasing order.

2) Initialize two index variables to find the candidate elements in the sorted array.

(a) Initialize first to the leftmost index: l = 0

(b) Initialize second the rightmost index: r = ar_size-1

3) Loop while l < r.

(a) If (A[l] + A[r] == sum) then return 1

(b) Else if( A[l] + A[r] < sum ) then l++

(c) Else r--

4) No candidates in whole array - return 0

**Example:** Let Array be {1, 4, 45, 6, 10, -8} and sum to find be 16

Sort the array A = {-8, 1, 4, 6, 10, 45}

Initialize l = 0, r = 5

A[l] + A[r] ( -8 + 45) > 16 => decrement r. Now r = 10

A[l] + A[r] ( -8 + 10) < 2 => increment l. Now l = 1

A[l] + A[r] ( 1 + 10) < 16 => increment l. Now l = 2

A[l] + A[r] ( 4 + 10) < 14 => increment l. Now l = 3

A[l] + A[r] ( 6 + 10) == 16 => Found candidates (return 1)

**Implementation:**

```
# include <stdio.h>
# define bool int
void quickSort(int *, int, int);
bool hasArrayTwoCandidates(int A[], int arr_size, int sum)
{
int l, r;
/* Sort the elements */
quickSort(A, 0, arr_size-1);
/* Now look for the two candidates in the sorted
array*/
l = 0;
r = arr_size-1;
while(l < r)
{
if(A[l] + A[r] == sum)
return 1;
else if(A[l] + A[r] < sum)
l++;
else // A[i] + A[j] > sum
r--;
}
return 0;
}
/* Driver program to test above function */
int main()
{
int A[] = {1, 4, 45, 6, 10, -8};
int n = 16;
int arr_size = 6;
if( hasArrayTwoCandidates(A, arr_size, n))
printf("Array has two elements with sum 16");
else
printf("Array doesn't have two elements with sum 16 ");
getchar();
return 0;
}
/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING
PURPOSE */
void exchange(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition(int A[], int si, int ei)
{
int x = A[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++)
{
if(A[j] <= x)
{
i++;
exchange(&A[i], &A[j]);
}
}
exchange (&A[i + 1], &A[ei]);
return (i + 1);
}
/* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int A[], int si, int ei)
{
int pi; /* Partitioning index */
if(si < ei)
{
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}
```