---
# System prepended metadata

title: Dziel i zwyciężaj

---

# Dziel i zwyciężaj

:::success
[Link do zadań, które robiliśmy](https://files.wpmii.pl/2021-11-06-zadania.pdf?fbclid=IwAR0nC7RZyqYNTmFwd9xz3El5sUdLxkPrp8szBiFHWQO5dCqGXDgvEsv3MXo)
:::

## Ogólny schemat algorytmów dziel i zwyciężaj:
    
```
P - jakiś problem do rozwiązania

DzielIZwyciężaj(P):
    jeśli P jest wystarczająco mały:
        zwróć rozwiązanie P
    wpp:
        podziel P na P1, P2, ..., Pk
        zastosuj DzielIZwyciężaj(P1), DzielIZwyciężaj(P2), ..., DzielIZwyciężaj(Pk)
        wykorzystaj rozwiązania P1, P2, ..., Pk do stworzenia rozwiązania P
        zwróć rozwiązanie P
```

**UWAGA:** Poniższe algorytmy w większości są na tyle proste, że wydzielają tylko jeden podproblem (a raczej ignorują ten drugi), który jest o połowę mniejszy od głównego i rozwiązanie problemu głównego wyznaczają na podstawie rozwiązania tylko tego jednego podproblemu.

Tylko wyszukiwanie minimum i maksimum używa rozwiązań obu podbroblemów.

## Wyszukiwanie binarne

- Szukamy zadanego elementu w posortowanej tablicy
- Korzystamy z faktu, że dla dowolnego elementu w tablicy, po lewej od niego są wyłącznie elementy niewiększe, a po prawej - niemniejsze.
- Z każdą iteracją zmniejszamy przedział poszukiwań o połowę

### Indeks szukanego elementu, jeśli jest w tablicy, -1 w przeciwnym przypadku

#### C++
```cpp=
int binarySearch(int arr[], int l, int r, int x) {
  while (l <= r) {
    int m = (l + r) / 2;
    if (arr[m] == x) {
      return m;
    }

    if (arr[m] > x) {
      r = m - 1;
    } else {
      l = m + 1;
    }
  }

  return -1;
}
```

#### Python
```python=
def binarySearch(list, l, r, x):
  while l <= r:
    m = floor((l + r) / 2)
    if list[m] == x:
      return m

    if list[m] > x:
      r = m - 1
    else:
      l = m + 1
  
  return -1
```

### Indeks pierwszego elementu niemniejszego od szukanego
**UWAGA:** Te funkcje dla szukanych wartości większych niż największa wartość w tablicy i tak zwracają ostatni indeks tablicy. Można się przed tym zabezpieczyć, sprawdzając, czy 
```x > tablica[r]``` i zwracając coś innego, jeśli będzie to prawdą.

#### C++
```cpp=
/* Komentarze opisują co się zmienia w porównaniu z wersją podstawową */
int binarySearch(int arr[], int l, int r, int x) {
  while (l < r) { // < zamiast <=, chcemy skończyć, gdy l == r
    int m = (l + r) / 2;
    /* nie sprawdzamy czy arr[s] == x,
     * bo wartości mogą się powtarzać i pierwsza szukana może być dalej z lewej,
     * więc nie chcemy kończyć po znalezieniu dowolnego elementu rówego x
     */
    if (arr[m] < x) {
      l = m + 1;
    } else {
      r = m; // m zamiast m - 1, bo arr[m] >= x, czyli jest potencjalnym rozwiązaniem
    }
  }

  return l; // zwracamy l - indeks, na którym skończyliśmy wyszukiwanie
}
```

#### Python
```python=
# Komentarze opisują co się zmienia w porównaniu z wersją podstawową
def binarySearch(list, l, r, x):
  while l < r: # < zamiast <=, chcemy skończyć, gdy l == r
    m = floor((l + r) / 2)
    # nie sprawdzamy czy arr[s] == x,
    # bo wartości mogą się powtarzać i pierwsza szukana może być dalej z lewej,
    # więc nie chcemy kończyć po znalezieniu dowolnego elementu rówego x
    if list[m] < x:
      l = m + 1
    else:
      r = m # m zamiast m - 1, bo arr[m] >= x, czyli jest potencjalnym rozwiązaniem
  
  return l # zwracamy l - indeks, na którym skończyliśmy wyszukiwanie
```



### Indeks pierwszego elementu niewiększego od szukanego

**UWAGA:** W tym wariancie do obliczania ```m``` musimy używać funkcji ```ceil```(sufit), która w C++ znajduje się w bibliotece ```cmath```, a w pythonie w ```math```.

Zaokrąglanie w dół nie zadziała, ponieważ w przypadku, gdy zakres przeszukiwań będzie dwuelementowy (```l == r - 1```), obliczona wartość ```m``` zawsze będzie równa ```l```, więc wykonując instrukcję ```l = m```, nic nie zmienimy.

Używając zaokrąglania w górę, w takiej sytuacji obliczona wartość ```m``` będzie równa ```r``` zatem obie z instrukcji ```r = m - 1```, ```l = m``` zmniejszą przedział poszukiwań.

#### C++
```cpp=
int binarySearch(int arr[], int l, int r, int x) {
  while (l < r) {
    int m = ceil((l + r) / 2);
      
    if (arr[m] > x) {
      r = m - 1;
    } else {
      l = m;
     
  }

  return l;
}
```

#### Python
```python=
def binarySearch(list, l, r, x):
  while l < r:
    m = ceil((l + r) / 2)

    if list[m] > x:
      r = m - 1
    else:
      l = m
  
  return l
```

### Wersja podstawowa rekurencyjnie

#### C++
```cpp=
int binarySearch(int arr[], int l, int r, int x) {
  if (l > r) {
    return -1;
  }

  int s = (l + r) / 2;

  if (arr[s] == x) {
    return s;
  }

  if (arr[s] > x) {
    return binarySearch(arr, l, s - 1, x);
  }

  return binarySearch(arr, s + 1, r, x);
}
```

#### Python
```python=
def binarySearch(list, l, r, x):
  if l > r:
    return -1

  s = floor((l + r) / 2)

  if list[s] == x:
    return s
  
  if list[s] > x:
    return binarySearch(list, l, s - 1, x)

  return binarySearch(list, s + 1, r, x)

```

## Szybkie potęgowanie

- Obliczamy $a^n$
- Korzystamy z binarnej reprezentacji $n$, domnażając $a^k$ do wyniku, jeśli $k$-ty od prawej bit $n$ jest jedynką.

### Iteracyjnie

#### C++
```cpp=
int fastExp(int a, int n) {
  if (n == 0) {
    return 1;
  }

  int result = 1;
  while (n > 0) {
    if (n % 2 == 1) {
      result *= a;
    }

    a *= a;
    n /= 2;
  }

  return result;
}
```

#### Python
```python=
def fastExp(a, n):
  if n == 0:
    return 1

  result = 1
  while n > 0:
    if n % 2 == 1:
      result *= a

    a *= a
    n = floor(n / 2)
  
  return result
```

### Rekurencyjnie

#### C++
```cpp=
int fastExp(int a, int n) {
  if (n == 0) {
    return 1;
  }

  if (n % 2 == 1) {
    return fastExp(a * a, n / 2) * a;
  }

  return fastExp(a * a, n / 2);
}
```

#### Python
```python=
def fastExp(a, n):
  if n == 0:
    return 1

  if n % 2 == 1:
    return fastExp(a * a, floor(n / 2)) * a

  return fastExp(a * a, floor(n / 2))
```

## Wyznaczanie miejsc zerowych funkcji

- Znamy wykres funkcji, ale nie znamy dokładnie miejsc zerowych
- Zmniejszamy przedział poszukiwań o połowę, tak żeby miejsce zerowe ciągle się w nim zawierało
- Korzystamy z faktu, że jeśli $f(a) * f(b) < 0$, to pomiędzy $a$ i $b$ jest miejsce zerowe
- Kończymy, gdy znajdziemy się wystarczająco blisko zera

#### C++
```cpp=
/* Jakaś zadana z góry funkcja */
double f(double x) {
  return sin(x) + pow(x, 2) - pow(x, 3) - 0.5;
}

/* Dokładność z jaką chcemy obliczyć miejsce zerowe */
double EPSILON = 0.00001;

double zero(double l, double r) {
  double m = (l + r) / 2.0;

  while(abs(f(m)) > EPSILON) {
    if (f(l) * f(m) < 0) {
      r = m;
    } else {
      l = m;
    }

    m = (l + r) / 2;
  }

  return m;
}
```

#### Python
```python=
# Jakaś zadana z góry funkcja
def f(x):
  return sin(x) + x**2 - x**3 - 0.5

# Dokładność z jaką chcemy obliczyć miejsce zerowe
EPSILON = 0.00001

def zero(l, r):
  m = (l + r) / 2

  while abs(f(m)) > EPSILON:
    if f(l) * f(m) < 0:
      r = m
    else:
      l = m
    m = (l + r) / 2
  
  return m
```

## Jednoczesne wyszukiwanie wartości minimalnej i maksymalnej

> Tego nie zdążyliśmy przerobić na wykładzie

- Szukamy minimum i maksimum w dowolnej tablicy
- Dzielimy tablicę na pół i znajdujemy min i max osobno dla lewej i prawej połowy
- Porównujemy znalezione wartości i zwracamy mniejszego mina oraz większego maxa
- Przypadkiem bazowym będzie sytuacja, gdy nasz przedział poszukiwań jest jedno lub dwuelementowy - wtedy znalezienie mina i maxa jest trywialne

#### C++
```cpp=
/* Jako że nie możemy z funkcji zwrócić dwóch wartości to pakujemy je do pair
 * pair to po prostu ładna reprezentacja pary liczb
 * <int, int> to typy wartości jakie będziemy przechowywać w parze
 * make_pair(a, b) tworzy parę przechowującą wartości a i b
 * Do elementów pary odwołujemy się przez .first oraz .second
 */ 

/* Pierwszy element pary będzie min, drugi max */
pair<int, int> minMax(int arr[], int l, int r) {
  int min, max;

  /* Przypadek bazowy */
  if (l == r) {
    min = max = arr[l];
  } else if (l == r - 1) {
    if (arr[l] > arr[r]) {
      min = arr[r];
      max = arr[l];
    } else {
      min = arr[l];
      max = arr[r];
    }
  } else {
    /* Dzielimy przedział na pół */
    int m = (l + r) / 2;
      
    /* Znajdujemy rozwiązania dla obu podproblemów (połówek) */
    pair<int, int> lMinMax = minMax(arr, l, m);
    pair<int, int> rMinMax = minMax(arr, m + 1, r);

    /* Korzystamy z roziązań podproblemów to obliczania rozwiązania problemu głównego */
    if (lMinMax.first < rMinMax.first) {
      min = lMinMax.first;
    } else {
      min = rMinMax.first;
    }
    
    if (lMinMax.second > rMinMax.second) {
      max = lMinMax.second;
    } else {
      max = rMinMax.second;
    }
  }
  
  return make_pair(min, max);
}
```

#### Python
```python=
 # Jako że nie możemy z funkcji zwrócić dwóch wartości to pakujemy je do krotki
 # krotka to taka lista, ale nie da się zmieniać jej elementów po stworzeniu
 # (a, b) tworzy krotkę przechowującą wartości a i b 
 # (można przechowywać więcej wartości)
 # Do elementów krotki odwołujemy się jak w przypadku listy przez krotka[indeks]

# Pierwszy element krotki będzie min, drugi max
def minMax(list, l, r):
  min, max = None, None

  # Przypadek bazowy
  if l == r:
    min = max = list[l]
  elif l == r - 1:
    if list[l] > list[r]:
      min = list[r]
      max = list[l]
    else:
      min = list[l]
      max = list[r]
  else:
    # Dzielimy przedział na pół
    m = floor((l + r) / 2)
    
    # Znajdujemy rozwiązania dla obu podproblemów (połówek)
    lMinMax = minMax(list, l, m)
    rMinMax = minMax(list, m + 1, r)

    # Korzystamy z roziązań podproblemów to obliczania rozwiązania problemu głównego
    if lMinMax[0] < rMinMax[0]:
      min = lMinMax[0]
    else:
      min = rMinMax[0]
    
    if lMinMax[1] > rMinMax[1]:
      max = lMinMax[1]
    else:
      max = rMinMax[1]

  return (min, max)
```