Cautare Binara - Teorie

Cautare Binara - Teorie

Binary Search
------------


Cautarea binara este un algoritm eficient de cautare a unui element intr-un array sortat, care functioneaza prin injumatatirea repetata a spatiului de cautare.


Cum functioneaza?

- se porneste cu intregul array;
- se gaseste elementul din mijloc
- daca elementul din mijloc este egal cu TARGET -> am gasit elementul!
- daca Target-ul este mai mare ----> cautam in jumatatea DREAPTA
- Daca Target--ul este mai mic --> cautam in jumatatea STANGA
- Se repeta pana cand elementul este gasit sau spatiul de cautare devine gol.

arr = [2, 3,  4, 10, 40]
//     0  1   2   3   4 

Target = 10

middle = (0 + 4) / 2 = 2

cautam in jumatatea dreapta a spatiului de cautare pentru ca 10 > middle(4)

middle(2+4/2) am gasit elementul pe arr[3] Am gasit. 

index = 3

Cautare Liniara: O(n)

Complexitate O(log n)