Recorrido en espiral de matricse

Para recorrer una matriz en espiral, se simula el avance capa a capa mediante cuatro límites: superior, inferior, izquierdo y derecho. El bucle principal continúa mientras los límites no se crucen, procesando los bordes de cada capa. Cuando los límites coinciden, se detiene el recorrido espiral y se manejan los elementos restantes en una fila o columna.

class SolucionEspiral {
    public List<integer> recorrerEspiral(int[][] matriz) {
        int limiteSuperior = 0;
        int limiteInferior = matriz.length - 1;
        int limiteIzquierdo = 0;
        int limiteDerecho = matriz[0].length - 1;
        List<integer> resultado = new ArrayList<>();

        while (limiteSuperior < limiteInferior && limiteIzquierdo < limiteDerecho) {
            for (int columna = limiteIzquierdo; columna < limiteDerecho; columna++) 
                resultado.add(matriz[limiteSuperior][columna]);
            for (int fila = limiteSuperior; fila < limiteInferior; fila++) 
                resultado.add(matriz[fila][limiteDerecho]);
            for (int columna = limiteDerecho; columna > limiteIzquierdo; columna--) 
                resultado.add(matriz[limiteInferior][columna]);
            for (int fila = limiteInferior; fila > limiteSuperior; fila--) 
                resultado.add(matriz[fila][limiteIzquierdo]);
            limiteIzquierdo++;
            limiteDerecho--;
            limiteSuperior++;
            limiteInferior--;
        }

        if (limiteSuperior == limiteInferior) {
            for (int columna = limiteIzquierdo; columna <= limiteDerecho; columna++) 
                resultado.add(matriz[limiteSuperior][columna]);
        } else if (limiteIzquierdo == limiteDerecho) {
            for (int fila = limiteSuperior; fila <= limiteInferior; fila++) 
                resultado.add(matriz[fila][limiteIzquierdo]);
        }
        return resultado;
    }
}
</integer></integer>

Posición de inserción en búsqueda binaria

Dado un arreglo ordenado y sin elementos repetidos, se determina la posición donde insertar un valor objetivo. La búsqueda binaria con intervalos cerrados permite encontrar el índice exacto, optimizando con detección temprana si el objetivo está presente. El algoritmo retorna el índice izquierdo al finalizar el bucle.

class SolucionInsercion {
    public int encontrarPosicionInsercion(int[] arreglo, int objetivo) {
        int inicio = 0;
        int fin = arreglo.length - 1;
        while (inicio <= fin) {
            int medio = inicio + (fin - inicio) / 2;
            if (arreglo[medio] == objetivo) {
                return medio;
            } else if (arreglo[medio] > objetivo) {
                fin = medio - 1;
            } else {
                inicio = medio + 1;
            }
        }
        return inicio;
    }
}

Primera y última apparición de un elemento

En arreglos ordenados con duplicados, se utiliza búsqueda binaria modificada para localizar los límites de un valor objetivo. Para la primera aparición, se comprime el límite derecho cuando el objetivo es menor o igual; para la última, se comprime el límite izquierdo cuando el objetivo es mayor o igual. Se combinan ambas funciones para obtener el rango.

class SolucionRango {
    public int[] buscarRango(int[] arreglo, int objetivo) {
        int primeraPos = buscarPrimeraPosicion(arreglo, objetivo);
        int ultimaPos = buscarUltimaPosicion(arreglo, objetivo);
        if (primeraPos > ultimaPos) {
            return new int[]{-1, -1};
        }
        return new int[]{primeraPos, ultimaPos};
    }

    private int buscarPrimeraPosicion(int[] arreglo, int objetivo) {
        int inicio = 0;
        int fin = arreglo.length - 1;
        while (inicio <= fin) {
            int medio = inicio + (fin - inicio) / 2;
            if (objetivo <= arreglo[medio]) {
                fin = medio - 1;
            } else {
                inicio = medio + 1;
            }
        }
        return inicio;
    }

    private int buscarUltimaPosicion(int[] arreglo, int objetivo) {
        int inicio = 0;
        int fin = arreglo.length - 1;
        while (inicio <= fin) {
            int medio = inicio + (fin - inicio) / 2;
            if (objetivo >= arreglo[medio]) {
                inicio = medio + 1;
            } else {
                fin = medio - 1;
            }
        }
        return fin;
    }
}