Programa C para la técnica de dos punteros

Dos punteros es realmente una técnica fácil y efectiva que se usa típicamente para buscar pares en una array ordenada.
Dada una array ordenada A (ordenada en orden ascendente), que tiene N enteros, encuentre si existe algún par de elementos (A[i], A[j]) tal que su suma sea igual a X.

Veamos la solución ingenua .  

// Naive solution to find if there is a
// pair in A[0..N-1] with given sum.
#include <stdio.h>
  
int isPairSum(int A[],int  N,int X)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) 
        {
            // as equal i and j means same element
            if (i == j) 
                continue;
            
            // pair exists
            if (A[i] + A[j] == X)
                return true; 
  
            // as the array is sorted
            if (A[i] + A[j] > X)
                break; 
        }
    }
  
    // No pair found with given sum.
    return 0;
}
  
// Driver Code
int main()
{
    int arr[]={3,5,9,2,8,10,11};
    int val=17;
    int arrSize = sizeof(arr)/sizeof(arr[0]);
    
    // Function call
    printf("%d",isPairSum(arr,arrSize,val));
  
    return 0;
}

1

Complejidad Temporal:  O(n ² ).

Ahora veamos cómo funciona la técnica de dos puntos. Tomamos dos punteros, uno que representa el primer elemento y otro que representa el último elemento de la array, y luego sumamos los valores guardados en ambos punteros. Si su suma es menor que X, desplazamos el puntero izquierdo hacia la derecha o si su suma es mayor que X, desplazamos el puntero derecho hacia la izquierda para acercarnos a la suma. Seguimos moviendo los punteros hasta obtener la suma como X. 

#include <stdio.h>
  
// Two pointer technique based solution to find
// if there is a pair in A[0..N-1] with a given sum.
int isPairSum(int A[], int N, int X)
{
    // represents first pointer
    int i = 0;
  
    // represents second pointer
    int j = N - 1;
  
    while (i < j)
    {
        // If we find a pair
        if (A[i] + A[j] == X)
            return 1;
  
        // If sum of elements at current
        // pointers is less, we move towards
        // higher values by doing i++
        else if (A[i] + A[j] < X)
            i++;
  
        // If sum of elements at current
        // pointers is more, we move towards
        // lower values by doing j--
        else
            j--;
    }
    return 0;
}
  
// Driver code
int main()
{
    // array declaration
    int arr[] = { 3, 5, 9, 2, 8, 10, 11 };
      
    // value to search
    int val = 17;
      
    // size of the array
    int arrSize = sizeof(arr) / sizeof(arr[0]);
    
    // Function call
    printf("%d", isPairSum(arr, arrSize, val));
  
    return 0;
}