Algoritmi: Metoda bisecţiei

Să zicem că avem funcţia \(f(x) = 3{x} + 3\) şi vrem să găsim acel \(x\) pentru care ecuaţia \(f(x) = 0\) este adevărată, adică vrem să-i găsim rădăcina.
O primă metodă ar fi să alegem un interval unde credem că s-ar afla acest \(x\), să luăm pe rând toate valorile din interval şi să vedem pentru care valoare \(f(x) = 0\) este adevărată. Acest algoritm necesită \(O(n)\) timp de execuţie. Îl putem face şi mai rapid. Cum? Prin metoda bisecţiei.
Metoda bisecţiei constă în reducerea intervalului de căutare prin înjumătăţirea repetată şi selectarea subintervalului în care se găseşte rădăcina. Din acest motiv algoritmul este logaritmic \(O(\log{n})\). Algoritmul este similar cu căutarea binară.
Ca metoda să funcţioneze trebuie ca funcţia, căreia vrem să-i găsim rădăcina, să fie continuă.
Conform teoremei Cauchy-Bolzano (teorema valorii intermediare) dacă \(f\) (o funcţie oarecare) este continuă pe intervalul \([a, b]\) şi \(f(a)\) şi \(f(b)\) au semne opuse, adică \(f(a) * f(b) < 0\), atunci există o valoare \(c\) din intervalul \((a, b)\) pentru care \(f(c) = 0\).
Este evident, deoarece dacă la extremităţi funcţia are semne opuse atunci undeva graficul intersectează axa \(Ox\). Graficul funcţiei \(f(x) = 3{x} + 3\) este următorul:

Observaţi că intersectează axa \(Ox\) în punctul -1.
Pentru această funcţie voi alege intervalul \([a, b]\) - \(a, b\) numere reale. Intervalul va fi împărţit în două subintervale: \([a, c]\) şi \([c, b]\), unde \(c = \frac{(a + b)}{2}\). Căutarea rădăcinii se va face în subintervalul în care funcţia \(f(x) = 3{x} + 3\) îşi schimbă semnul, astfel:

• Dacă \(f(a) * f(c) < 0\), atunci căutarea continuă în intervalul \([a, c]\);
• Altfel căutarea continuă în intervalul \([c, b]\).

Procesul se termină atunci când se ajunge la intervalul \([a, b]\) pentru care \(b-a < sigma\), unde \(sigma\) este eroarea acceptată pentru o precizie de 5 zecimale şi are valoarea 0.00001. Nu uitaţi că calculele cu float şi double nu sunt foarte precise, de aceea trebuie să luăm în considerare o marjă de eroare.

#include <iostream>
using namespace std;

// Functia f
double f(double x) 
{
    return 3*x + 3;
}

double sigma = 0.00001;

// Metoda bisectiei
double getRoot(double a, double b)
{
    double c;
    if(b-a < sigma) return (a+b) / 2.0; // S-a gasit radacina, o returnez
    else
    {
        c = (a+b) / 2.0; 
        if(f(a) * f(c) < 0) return getRoot(a, c);
        else return getRoot(c, b);
    }
}

int main()
{
    // Se va afisa -0.999999 care este foarte aproape de -1
    cout << getRoot(-10, 10);
    system("PAUSE");
    return 0;
}

Algoritmi: Căutarea Binară

Căutarea binară (Binary Search) este un algoritm care caută poziţia unei valori într-o colecţie de date, sau vector, sortată. La fiecare pas, algoritmul compară valoarea căutată cu valoarea din mijlocul vectorului. Dacă se potrivesc atunci indicele sau poziţia valorii în vector este returnată. În caz contrar se caută în subvectorul din stânga valorii din mijloc, dacă valoarea căutată este mai mică decât cea din mijloc, sau în subvectorul din dreapta, dacă este mai mare. Algoritmul repetă aceiaşi paşi pentru fiecare subvector. Dacă nu se găseşte valoarea se va returna valoarea -1.
Complexitatea algoritmului este \(O(\log{n})\) (logaritmic) deoarece la fiecare pas vectorul este înjumătăţit.

Implementare în C++

// *** Binary Search *** //
// d (dreapta) - limita inferioara 
// s (stanga) - limita superioara
int cauta(int d, int s, int key, int * v)
{
    if(s < d) return -1; // Nu s-a gasit nicio valoare
    int m = (d + s) / 2; // Elementul din mijloc
    if(key < v[m]) return cauta(d, m-1, key, v); // Cauta in subvectorul din stanga
    else if(key > v[m]) return cauta(m+1, s, key, v); // Cauta in subvectorul din dreapta
    else return m; // Gasit!
}

Exemplu:

#include <iostream>
using namespace std;

// *** Binary Search *** //
// d (dreapta) - limita inferioara 
// s (stanga) - limita superioara
int cauta(int d, int s, int key, int * v)
{
    if(s < d) return -1; // Nu s-a gasit nicio valoare
    int m = (d + s) / 2; // Elementul din mijloc
    if(key < v[m]) return cauta(d, m-1, key, v); // Cauta in subvectorul din stanga
    else if(key > v[m]) return cauta(m+1, s, key, v); // Cauta in subvectorul din dreapta
    else return m; // Gasit!
}

int main()
{
    int iteme[] = {2, 9, 11, 15, 28, 33, 40, 47, 51, 64, 76, 77, 82, 85, 94}; // 15 elemente
    int indice = cauta(0, 14, 76, iteme);
    cout << indice; // 10; iteme[10] == 76;
    
    system("PAUSE");
    return 0;
}