Classe de busca em vetores genéricos em C++
O algoritmo a seguir fornece uma classe capaz de realizar uma busca num vetor qualquer.
Através de templates, um objeto da classe Busca pode trabalhar com qualquer tipo de dado que um determinado vetor estiver armazenando através de um único método. Não tendo, portanto, a necessidade de se criar métodos específicos.
Como exemplo, o programa cria um vetor v[] de caracteres e um outro v2[] de números inteiros e realiza a busca, com o objeto Buscador, tanto recursivamente quanto iterativamente.
1/* Escrito por Lucas Stefano
2 */
3
4#include <iostream>
5using namespace std;
6
7class Busca {
8public:
9 template <class tipo> int iterativa (tipo x, int n, tipo *v);
10 template <class tipo> int recursiva (tipo x, int n, tipo *v);
11};
12
13/* As duas funções abaixo recebem x, n e v[0...n-1].
14 * Devolvem um índice k tal que v[k] = x. Mas, se tal k
15 * não existir, devolvem -1. */
16
17template <class tipo>
18int Busca::iterativa (tipo x, int n, tipo *v) {
19 int k = n - 1;
20 for (k; k >= 0 && v[k] != x; k--);
21 return k;
22}
23
24template <class tipo>
25int Busca::recursiva (tipo x, int n, tipo *v) {
26 return (n == 0 || v[n-1] == x) ? n-1 : recursiva (x, n-1, v);
27}
28
29int main () {
30 char v[] = {'a', 'b', 'v', 'j', 'h', 'w', 'x'};
31 int v2[] = {3, 4, 2, 8, 19, 34, 77, 88};
32 Busca Buscador;
33
34 cout << "Busca iterativa: índice do char 'v' em v[]: " << Buscador.iterativa ('v', 7, v);
35 cout << "\n";
36 cout << "Busca iterativa: índice do int 19 em v2[]: " << Buscador.iterativa (19, 8, v2);
37 cout << "\n\n";
38 cout << "Busca recursiva: índice do char 'v' em v[]: " << Buscador.recursiva ('v', 7, v);
39 cout << "\n";
40 cout << "Busca recursiva: índice do int 19 em v2[]: " << Buscador.recursiva (19, 8, v2);
41 cout << "\n";
42
43 return 0;
44}