Busca exponencial

En Ciències de la Computació, una busca exponencial (també cridat busca galopante o busca Struzik) és un algoritme, creat per Jon Bentley i Andrew Chi-Chih Yao en 1976, per a buscar en llistes infinites/no acotades ordenades. Hi ha numeroses maneres per a implementar-ho sent la més comuna determinar el ranc en que la clau de busca residix i realisar una busca binaria dins de dit ranc. Açò demora O(log i) on i és la posició de la clau de busca en la llista, si la clau de busca està en la llista, o la posició a on la clau de busca deuria estar, si la clau de busca no està en la llista.

La busca exponencial també pot ser usada en llistes acotades. La busca exponencial pugues inclús millorar els temps d'algoritmes de busca en llistes acotades, com a busca binaria, quan l'element buscat està prop del principi del array. Açò és perque la busca exponencial correrà en O(log i), a on i és l'índex de l'element buscat en la llista, mentres que la busca binaria correria en O(log n), a on n és el número d'elements en la llista.

Algoritme

La busca exponencial permet buscar a través d'una llista no acotada ordenada per a un valor d'entrada especificat (la clau de busca). L'algoritme consistix en dos etapes. La primera etapa determina un ranc en el que la clau de busca residiria si estiguera en la llista. En la segona etapa, es realisa una busca binaria en eixe ranc. En la primera etapa, suponent que la llista està ordenada en orde ascendent, l'algoritme busca el primer exponent j, a on el valor

$2^j$

és més gran que la clau de busca. Este valor,

$2^j$

es convertix en el llímit superior per a la busca binaria en el poder anterior de 2,

$2^{j-1}$

, sent el llímit inferior per a la busca binaria.

// Torna la posició de la clau key en el array arr de tamany size.
template <typename T>
int exponential_search(T arr[], int size, T key)
{
    if (size == 0) {
        return NOT_FOUND;
    }

    int bound = 1;
    while (bound < size && arr[bound] < key) {
        bound *= 2;
    }

    return binary_search(arr, key, bound/2, min(bound, size));
}

En cada pas, l'algoritme compara la clau de busca en el valor en l'índex de la busca actual. Si l'element en l'índex actual és més chicotet que la clau de busca, l'algoritme torna a eixecutar-se, botant-se el següent índex de busca doblant-ho, calculant la següent potència de 2. Si l'element en l'índex actual és major que la clau de busca, l'algoritme ara sap que la clau de busca, si està contingut en la llista en absolut, està localisat en l'interval format per l'índex de busca anterior,

$2^{j-1}$

, i l'índex de busca actual,

$2^j$

. La busca binaria s'eixecuta llavors en el resultat d'un fracàs, si la clau de busca no està en la llista, o la posició de la clau de busca en la llista.

Rendiment

La primera etapa de l'algoritme demora O(log i), a on i és l'índex a on la clau de busca estaria en la llista. Açò és perque, per a determinar el llímit superior per a la busca binaria, el bucle s'eixecuta exactament $\lceil \log i\rceil$ voltes. Com la llista està ordenada, despuix de doblar l'índex de busca $\lceil \log i\rceil$ voltes, l'algoritme estarà en un índex de busca que és més gran que o igual que i quan $2^{\lceil \log (i)\rceil }\ge i$. D'esta forma, la primera etapa de l'algoritme demora O(log i).

La segona part de l'algoritme també demora O(log i). Quan la segona etapa és senzillament una busca binaria, demora O(log n) a on n és el tamany de l'interval a on es va realisar la busca. El tamany d'este interval seria $2^j-2^{j-1}$ a on, com es va vore abans, j = log i. Açò significa que el tamany de l'interval sent explorat és $2^{\log i}-2^{\log i-1}=2^{\log i-1}$. Açò nos dona un temps d'eixecució de $\log (2^{logi-1})=\log i-1=O(\log i)$.

Açò li dona a l'algoritme un temps d'eixecució total, calculat sumant els temps de les dos etapes, de$O(\log i)+O(\log i)=2O(\log i)=O(\log i)$.

Vore també

• Busca llineal
• Busca binaria
• Busca d'interpolació

• Busca ternaria
• Taula Hash