> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.

# Divide y vencerás en C: máximo, suma, búsqueda binaria y recurrencias

> El esquema divide y vencerás explicado con vectores en C: caso trivial, dividir, resolver y combinar, árbol de subproblemas, búsqueda binaria y cálculo del coste con ecuaciones de recurrencia.

<Card title="Abrir el simulador" icon="flask" href="https://simulab.es/programacion/divide-y-venceras">
  Máximo, suma, vector creciente y búsqueda binaria en C, con el trozo de cada llamada y su coste.
</Card>

Ante un problema grande, una estrategia clásica es **partirlo** en trozos más pequeños del mismo tipo, resolver cada uno y **juntar** los resultados. Así funcionan merge sort, quicksort, la búsqueda binaria, la multiplicación rápida de números grandes o la transformada rápida de Fourier.

## Lo que vas a aprender

* El esquema general de divide y vencerás.
* Cómo se aplica a vectores dividiendo por la mitad.
* La búsqueda binaria.
* Calcular el coste con ecuaciones de recurrencia.
* Cuándo compensa y cuándo no.

## Cómo se usa el simulador

* Elige el problema: **máximo**, **suma**, **¿creciente?** o **búsqueda binaria**.
* **Datos**: número de elementos (2 – 16) y disposición: aleatorio, creciente o casi creciente. **🎲 Nuevos datos** genera otros.
* Avanza con **⏮**, **◀**, **▶ Ejecutar**, **▶** y **⏭**.
* Se resalta el **trozo** del vector que trata cada llamada y su mitad, la línea del **código** en C y el **árbol de subproblemas**. Los contadores dan las llamadas, las comparaciones y el tamaño de la pila.
* **Cómo funciona** muestra la ecuación de recurrencia y su solución.

## Fundamentos teóricos

### El esquema

```text theme={null}
resolver(problema):
    si es trivial: devolver su solución directa
    dividir en subproblemas más pequeños
    resolver cada subproblema (recursivamente)
    combinar las soluciones
```

### Con vectores

```c theme={null}
int maximo(int V[], int ini, int fin) {
    if (ini == fin) return V[ini];            // caso trivial
    int mitad = (ini + fin) / 2;              // dividir
    int izq = maximo(V, ini, mitad);          // resolver
    int der = maximo(V, mitad + 1, fin);
    return izq > der ? izq : der;             // combinar
}
```

### Búsqueda binaria

En un vector **ordenado**, se mira el centro: si es el buscado, termina; si es mayor, se busca solo en la mitad izquierda; si es menor, en la derecha. **Solo se resuelve una mitad**.

### Ecuaciones de recurrencia

El coste $T(n)$ se expresa en función del coste de los subproblemas:

| Problema | Recurrencia | Coste |
| - | - | - |
| Máximo, suma | $T(n) = 2T(n/2) + O(1)$ | $O(n)$ |
| Búsqueda binaria | $T(n) = T(n/2) + O(1)$ | $O(\log n)$ |
| Merge sort | $T(n) = 2T(n/2) + O(n)$ | $O(n\log n)$ |

Regla general (teorema maestro simplificado) para $T(n) = a\,T(n/b) + O(n^k)$:

* Si $a < b^k$: $O(n^k)$.
* Si $a = b^k$: $O(n^k\log n)$.
* Si $a > b^k$: $O(n^{\log_b a})$.

### ¿Cuándo compensa?

Buscar el máximo por divide y vencerás hace las mismas $n - 1$ comparaciones que un bucle: no gana nada. Compensa cuando **la combinación aprovecha el trabajo** (merge sort frente a ordenación por inserción) o cuando se **descarta** parte del problema (búsqueda binaria).

## Ejemplos resueltos

<AccordionGroup>
  <Accordion title="Ejemplo 1 · Máximo de {4, 9, 2, 7}" defaultOpen>
    maximo(0, 3) → maximo(0, 1) y maximo(2, 3). maximo(0, 1) = max(4, 9) = 9; maximo(2, 3) = max(2, 7) = 7. Resultado: max(9, 7) = 9.

    7 llamadas y 3 comparaciones ($n - 1$).
  </Accordion>

  <Accordion title="Ejemplo 2 · Búsqueda binaria">
    En un vector ordenado de 1000 elementos, la búsqueda binaria necesita como mucho $\lceil\log_2 1001\rceil = 10$ comparaciones. Una búsqueda secuencial, hasta 1000.
  </Accordion>

  <Accordion title="Ejemplo 3 · Recurrencia de merge sort">
    $T(n) = 2T(n/2) + n$: $a = 2$, $b = 2$, $k = 1$, así que $a = b^k$ y $T(n) = O(n\log n)$.
  </Accordion>
</AccordionGroup>

## Experimenta con el simulador

<Steps>
  <Step title="El árbol">
    Con el máximo y 8 elementos, cuenta las llamadas del árbol. ¿Cuántas son con 16?
  </Step>

  <Step title="Binaria">
    Con la búsqueda binaria, mira cuántas llamadas hace con 16 elementos.
  </Step>

  <Step title="¿Creciente?">
    Con datos casi crecientes, mira dónde se detecta el fallo.
  </Step>
</Steps>

## Errores frecuentes

* **Calcular mal la mitad** y dejar trozos vacíos o solapados.
* **Olvidar el caso trivial.**
* **Aplicar búsqueda binaria a un vector desordenado.**

## Herramientas relacionadas

<CardGroup cols={3}>
  <Card title="Recursión en C" icon="arrows-rotate" href="/programacion/c/recursion">
    La base de divide y vencerás.
  </Card>

  <Card title="Algoritmos de ordenación" icon="arrow-down-wide-short" href="/programacion/algoritmos/ordenacion">
    Merge sort y quicksort.
  </Card>

  <Card title="Mejor y peor caso" icon="stopwatch" href="/programacion/c/mejor-peor-caso">
    Medir el coste.
  </Card>
</CardGroup>


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.