Problema 21: Índice del Pico en un Arreglo de Montaña

Enlace del problema: 852. Peak Index in a Mountain Array - LeetCode

Descripción: Se proporciona un arreglo de montaña donde existe un índice que satisface: arr[i] > arr[i-1] y arr[i] > arr[i+1]. Devuelve ese índice del pico.

Enfoque mediante búsqueda binaria

En lugar de un enfoque de fuerza bruta, analizamos las características del arreglo:

• El pico cumple: arr[medio] > arr[medio-1] y arr[medio] > arr[medio+1].
• En el lado izquierdo del pico, el arreglo es creciente: arr[i] > arr[i-1] y arr[i] < arr[i+1].
• En el lado derecho, el arreglo es decreciente: arr[i] < arr[i-1] y arr[i] > arr[i+1].

Aplicamos búsqueda binaria comparando el valor en medio con su vecino:

• Si mountain[medio] > mountain[medio-1], el pico está a la derecha, así que ajustamos ini = medio.
• De lo contrario, el pico está a la izqueirda, ajustamos fin = medio - 1.

Código en C++

class Solution {
public:
    int findPeakMountainIndex(vector<int>& mountain) {
        int ini = 1;
        int fin = mountain.size() - 2;
        while (ini < fin) {
            int medio = ini + (fin - ini + 1) / 2;
            if (mountain[medio] > mountain[medio - 1]) {
                ini = medio;
            } else {
                fin = medio - 1;
            }
        }
        return ini;
    }
};

Problema 22: Encontrar un Pico en un Arreglo

Enlace del problema: 162. Find Peak Element - LeetCode

Descripción: Dado un arreglo donde nums[i] ≠ nums[i+1], encuentra un índice que sea un pico (mayor que sus vecinos). Se asume que nums[-1] = nums[n] = -∞.

Enfoque mediante búsqueda binaria

La clave es identificar la "bipartición": para cualquier punto i, comparamos con i+1:

• Si nums[i] > nums[i+1], entonces en el lado izquierdo (incluyendo i) debe existir un pico, ya que el borde izquierdo es -∞.
• Si nums[i] < nums[i+1], entonces en el lado derecho (incluyendo i+1) debe existir un pico.

Esta propiedad permite aplicar búsqueda binaria para reducir el espacio de búsqueda.

Código en C++

class Solution {
public:
    int locatePeak(vector<int>& numbers) {
        int left = 0;
        int right = numbers.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (numbers[mid] > numbers[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};