Modelo de Memória de Arrays em Java

Diferentemente de linguagens como C ou C++, o Java não expõe diretamente ponteiros de memória ao desenvolvedor. O gerenciamento de endereços e a alocação são responsabilidades da Máquina Virtual Java (JVM). Por isso, não é possível visualizar o endereço físico exato de cada elemento durante a execução.

Ao imprimir um array em Java, o resultado exibe uma representação hash do objeto, não um endereço de memória cru. Em arrays multidimensionais, cada linha é, na verdade, um objeto array independente referenciado pelo array principal. Isso significa que não há garantia de continuidade física na memória para todos os elementos de uma matriz bidimensional, pois cada subarray pode ser alocado em regiões distintas do heap.

public static void validarMemoria() {
    int[][] matriz = {
        {10, 20, 30}, 
        {40, 50, 60}, 
        {70, 80, 90}
    };
    // Imprime as referências dos objetos array internos
    System.out.println(matriz[0]);
    System.out.println(matriz[1]);
    System.out.println(matriz[2]);
}

A saída mostrará hashes distintos para cada linha, confirmando que são objetos seeparados e não necessariamente contíguos na memória física.

Algoritmo 704: Busca Binária

Dado um array ordenado de inteiros e um valor alvo, o objetivo é encontrar o índice do alvo. Se não existir, retorna-se -1. A premissa básica exige que os dados estejam ordenados e, idealmente, sem duplicatas para garantir um resultado único.

O ponto crítico na implementação da busca binária é a definição consistente do intervalo de busca. Manter a invariantes do intervalo durante as iterações é essencial para evitar erros de limite.

Intervalo Fechado [inicio, fim]

Nesta abordagem, ambos os limites são inclusivos. O loop deve continuar enquanto o início for menor ou igual ao fim. Ao ajustar os limites, se o valor do meio for maior que o alvo, o novo limite superior torna-se o índice anterior ao meio.

class SolucaoBusca {
    public int localizar(int[] dados, int alvo) {
        int inicio = 0;
        int fim = dados.length - 1;
        
        while (inicio <= fim) {
            // Evita overflow usando soma diferencial
            int meio = inicio + ((fim - inicio) >> 1);
            
            if (dados[meio] == alvo) {
                return meio;
            } else if (dados[meio] > alvo) {
                fim = meio - 1;
            } else {
                inicio = meio + 1;
            }
        }
        return -1;
    }
}

Intervalo Semi-Aberto [inicio, fim)

Aqui, o limite direito é exclusivo. O loop opera enquanto o início for estritamente menor que o fim. Se o valor do meio exceder o alvo, o limite direito assume o valor do meio, pois o intervalo não inclui o limite superior.

Algoritmo 27: Remoção de Elementos

O desafio consiste em remover todas as ocorrências de um valor específico em um array, modificando a estrutura原地 (in-place) e retornando o novo comprimento. O uso de memória extra deve ser O(1).

Técnica de Ponteiros (Leitor e Escritor)

Utiliza-se dois indicadores para percorrer o array uma única vez. O ponteiro de leitura varre todos os elementos, enquanto o ponteiro de escrita marca a posição onde o próximo elemento válido deve ser armazenado.

class SolucaoRemocao {
    public int removerValor(int[] dados, int valorAlvo) {
        int escritor = 0;
        
        for (int leitor = 0; leitor < dados.length; leitor++) {
            if (dados[leitor] != valorAlvo) {
                dados[escritor] = dados[leitor];
                escritor++;
            }
        }
        return escritor;
    }
}

Alternativamente, pode-se usar ponteiros nas extremidades. Se o elemento inicial for igual ao valor alvo, substitui-se pelo elemento do fim e decrementa-se o ponteiro final. Caso contrário, avança-se o ponteiro inicial.

Algoritmo 977: Quadrados de Array Ordenado

Dado um array ordenado não decrescentemente, deve-se retornar um novo array com os quadrados de cada elemento, também odrenados. O desafio surge porque números negativos, ao serem elevados ao quadrado, podem resultar em valores maiores que os positivos.

Otimização com Dois Ponteiros

Como os maiores valores absolutos estarão nas extremidades do array original (início ou fim), podemos comparar os quadrados das extremidades e preencher um novo array de trás para frente.

class SolucaoQuadrados {
    public int[] quadradosOrdenados(int[] dados) {
        int n = dados.length;
        int[] resultado = new int[n];
        int inicio = 0;
        int fim = n - 1;
        int posicao = n - 1;
        
        while (inicio <= fim) {
            int quadEsq = dados[inicio] * dados[inicio];
            int quadDir = dados[fim] * dados[fim];
            
            if (quadEsq > quadDir) {
                resultado[posicao] = quadEsq;
                inicio++;
            } else {
                resultado[posicao] = quadDir;
                fim--;
            }
            posicao--;
        }
        return resultado;
    }
}

Esta abordagem evita a necessidade de ordenação explícita após o cálculo dos quadrados, reduzindo a copmlexidade de tempo para O(n).