Two Pointers - Algoritmo de busca

Esse é um algorítmo de fácil entendimento e também muito útil. Ele consiste em ter dois índices para percorrer um array, um índice no começo (esquerda) e outro no final (direita), e a cada interação, esses índices se aproximam um do outro. O índice inicial avança uma posição, e o índice do final regride uma posição.

Uma representação disso ficaria assim:

Obs. O array precisa ter os valores ordenados (sorted).

Um caso de uso muito comum desse algorítimo é quando você precisa procurar ou somar pares de valor.

Exemplo:

Em um array(A) de números inteiros de tamanho(N) ordenados de forma ascendente, procure se existe um par de elementos (A[i], A[j]) que a soma deles seja igual a X.

function existPairSum(A, N, X)
{
    var i = 0; // indice esquerdo
    var j = N - 1; // indice direito
 
    while (i < j) {
        if (A[i] + A[j] == X) {
            // se o par com a soma desejada é encontrado, retorna o par
            return A[i] + ' and ' + A[j]; 
        } else if (A[i] + A[j] < X) {
            // Se a soma dos elementos que estão sendo testados nessa interação
            // é menor que a soma desejada X, movemos o indice esquerdo para direita
            // incrementando i++
            i++;
        } else {
            // Se a soma dos elementos que estão sendo testados nessa interação
            // é maior que a soma desejada X, movemos o indice direito para esquerda
            // decrementando j--
        	j--;
        }
    }
  	
  	// Retorna false se não foi encontrado nenhum par de elemento que tenha a soma desejada
    return false;
}

// Usando a função

var myArray = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var sum = 11;
var arraySize = myArray.length;

existPairSum(myArray, arraySize, sum); // '2 and 9'

O algorítimo começa definindo os dois ponteiros/indices i,j (pointers), um em cada extremo do array(A), logo em seguida começa a primeira interação do loop while, somando os dois valores dos extremos. A primeira condição checa se a soma dos dois elementos atuais já satisfaz a soma desejada(X), se não, é checado se a soma dos elementos é menor que a desejada(X), se sim, nós movemos o primeiro ponteiro (pointer 1) para a direita, porém, se a soma é maior que a desejada(X) movemos o segundo ponteiro (pointer 2) para a esquerda, e vamos fazendo isso a cada interação, os ponteiros vão se movendo em direção ao outro, até acharmos o par que estamos procurando, ou então concluir que não existe um par que satisfaça a necessidade da soma desejada.

Vale ressaltar que a complexidade desse algoritimo, segundo a notação BIG-O (que é assunto para outra postagem) é O(n).

Para entender um pouco mais sobre Big-O Notation e complexidade de algoritimos, recomendo esse vídeo: https://www.youtube.com/watch?v=v4cd1O4zkGw

Se você já viu o vídeo, também recomendo um outro post aqui no tabnews falando sobre o assunto: https://www.tabnews.com.br/marcoshmendes/big-o-notation-conheca-as-complexidades-dos-algoritmos-mais-utilizados