Aula 5: Arrays e dois ponteiros

Imagine uma estante onde os livros ficam bem um ao lado do outro: quer o terceiro? Conte três e pule direto para ele. Isso é um array — acessar um item pelo índice é O(1). Hoje vamos conhecer um truque interessante, os 'dois ponteiros': em vez de um único marcador percorrendo tudo, você usa dois que

Dois ponteiros é como duas pessoas lendo uma fila longa a partir de extremidades opostas — uma começa do início e a outra do fim, e elas se movem uma em direção à outra até se encontrarem no meio. Assim você termina rápido, em vez de cada pessoa ler a fila inteira sozinha.

dois ponteiros: Um padrão em que dois índices se movem sobre um array (das extremidades para dentro ou na mesma direção) para resolver um problema em uma única passada.
in-place: Alterar os dados dentro da estrutura existente sem alocar uma nova — memória extra O(1).
memória contígua: Armazenar elementos lado a lado na memória, permitindo acesso por índice em O(1) e uma varredura eficiente para cache.