# 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++

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

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

#### C++

/* 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

# 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++

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

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++

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

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++

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

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++

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

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++

/* 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

# 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++

/* 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

# 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)