Busca binária

Esta página foi extraída (com algumas modificações) do capítulo 4 do livro de Eric Roberts, que trata de algoritmos recursivos.

A busca binária só faz sentido em vetores ordenados. Um vetor v[0..n-1] está em ordem crescente se

v[0]   <   v[1]   <   . . .   <   v[n-1] .

(Algumas pessoas preferem dizer "ordem não-decrescente", para enfatizar a diferença entre "<" e "<".)

O algoritmo

#define NAOEXISTE -1 // Recebe um número x e um vetor crescente // v[e..d] com n >= 0. Devolve j tal que v[j] == x // ou devolve NAOEXISTE se tal j não existe. int bb( int x, int v[], int e, int d) { if (e > d) return NAOEXISTE; else { int m; m = (e + d)/2; if (v[m] == x) return m; if (v[m] < x) return bb( x, v, m+1, d); else return bb( x, v, e, m-1); } }

Quanto tempo a função consome? Não é difícil perceber que o consumo de tempo é proporcional a

log₂ n, 

sendo n o número d-e+1.

Exercícios

1. Escreva uma versão iterativa da função bb. A função deve procurar um número x num vetor crescente v[0..n-1]. Documente sua função, ou seja, diga o que ela faz.

Busca binária em cadeias de caracteres

#include <string.h> // preciso de strcmp #define NONE -1 typedef char * string; // A função BinarySearch recebe uma cadeia de caracteres key e // um vetor array[low,high] de cadeias de caracteres cujos // elementos estão em ordem lexicográfica (ordem de dicionário). // A função devolve um índice de um elemento de array que seja // igual a key. Se tal índice não existe, a função devolve // NONE. int BinarySearch( string key, string array[], int low, int high) { int mid, cmp; if (low > high) return NONE; mid = (low + high) / 2; cmp = strcmp( key, array[mid]); if (cmp == 0 ) return mid; if (cmp < 0) return BinarySearch( key, array, low, mid - 1); else return BinarySearch( key, array, mid + 1, high); }

O livro de Eric Roberts não usa a função strcmp. Ele usa a função StringCompare de sua biblioteca particular strlib. O arquivo-interface da biblioteca está em strlib.h e a implementação está em strlib.c.

Exercícios

2. Escreva uma função que tenha o mesmo comportamento que strcmp.

3. [Roberts 2, p.190]  Escreva uma função recursiva que receba um inteiro positivo n e um inteiro não-negativo k e calcule  n^k.

4. [Roberts 9, p.193]  Escreva uma função recursiva que receba uma cadeia de caracteres e devolva o inverso da cadeia. Por exemplo, ao receber "algoritmo" a função deve devolver "omtirogla".