Um array é uma coleção de elementos armazenados de forma contígua na memória, ou seja, um bloco contínuo de endereços vizinhos.

Quando um array é declarado:

• o sistema aloca um bloco sequencial de memória
• o tamanho de cada posição depende do tipo armazenado (int, float, bool, etc.)
• cada elemento ocupa exatamente um índice

Essa organização contígua é o que torna o array extremamente eficiente para leitura.

Todo array possui um endereço base, que é o endereço do primeiro elemento.

Para acessar qualquer posição, o computador utiliza a seguinte lógica:

endereço do elemento = endereço_base + (índice × tamanho_do_tipo)

Ou seja, ele não precisa percorrer o array. Ele simplesmente calcula o endereço exato e acessa diretamente.

Acessar um elemento pelo índice é uma operação de tempo constante.

Complexidade: O(1)

Isso significa que, independentemente do array ter 10 ou 1 milhão de elementos, o custo da operação é o mesmo. O computador sabe exatamente onde ir.

Como os elementos estão em posições contíguas e não podem existir espaços entre eles, inserir um novo elemento pode exigir deslocamento de dados.

Inserção no Final

Se houver espaço disponível no bloco alocado, basta colocar o novo elemento na próxima posição e nenhum deslocamento é necessário.

Complexidade: O(1)

Inserção no Início ou no Meio

Todos os elementos posteriores precisam ser deslocados uma posição à frente e o array precisa abrir espaço para o novo item. Se o array possui N elementos, pode ser necessário mover até N elementos.

Complexidade: O(N)

A lógica é semelhante à inserção.

Deleção no Final

Basta reduzir o tamanho lógico do array e nenhum deslocamento é necessário.

Complexidade: O(1)

Deleção no Início ou no Meio

Os elementos seguintes precisam recuar uma posição e pode ser necessário deslocar N − 1 elementos.

Complexidade: O(N)

Se a remoção for no meio, em média deslocamos aproximadamente N/2 elementos, mas em análise Big O isso continua sendo O(N), pois constantes são desconsideradas.

Busca Linear

Na busca linear, o array é percorrido elemento por elemento até encontrar o valor desejado.

No pior caso, o elemento está na última posição ou não está presente. Isso exige percorrer todos os N elementos.

Complexidade: O(N)

O desempenho da busca linear cresce proporcionalmente ao tamanho do array.

Um array ordenado é simplesmente um array em que os elementos são mantidos em ordem — normalmente crescente ou decrescente.

A principal motivação para manter um array ordenado é facilitar e acelerar operações de busca, já que a posição relativa dos elementos passa a fornecer informações úteis durante a procura.

Considere o seguinte array:

Suponha que queremos encontrar o valor 22.

Ao analisar o primeiro elemento (10), sabemos que 22 só pode estar à direita, pois os elementos estão ordenados.

Quando verificamos o próximo valor (33), percebemos que ele já é maior que 22. Como o array está ordenado, isso significa que 22 não pode existir na estrutura, e a busca pode ser interrompida imediatamente.

Essa propriedade permite encerrar buscas mais cedo, economizando operações em comparação com um array não ordenado.

Mesmo assim, utilizando busca sequencial, a complexidade ainda é:

O(N)

A principal desvantagem de arrays ordenados aparece durante a inserção.

Para manter a ordenação, o novo elemento precisa ser posto na posição correta. Isso normalmente envolve duas etapas:

1. Encontrar o ponto onde o elemento deve ser inserido
2. Deslocar os elementos seguintes para abrir espaço

Por exemplo, ao inserir o valor 22 no array:

O resultado precisa ser:

Para isso, os elementos 33, 44 e 55 precisam ser deslocados uma posição à frente.

Devido a esse deslocamento, a complexidade da inserção continua sendo:

O(N)

Apesar do custo de inserção, arrays ordenados oferecem uma vantagem extremamente importante: possibilitam buscas muito mais eficientes.

Quando os dados estão ordenados, é possível utilizar busca binária, um algoritmo que reduz drasticamente o número de comparações necessárias para encontrar um elemento.

Enquanto a busca linear possui complexidade O(N), a busca binária possui complexidade O(log N), tornando-se muito mais eficiente para grandes volumes de dados.

Por isso, arrays ordenados são especialmente úteis em cenários onde:

• buscas são frequentes
• inserções são relativamente raras