buscavetor

INF1007: Programação 2
7 – Busca em Vetores

01/04/2014

(c) Dept. Informática - PUC-Rio

1

Tópicos Principais
• Busca em vetor
– Busca linear
– Busca binária

01/04/2014

(c) Dept. Informática - PUC-Rio

2

Busca em Vetor
• Busca em vetor:
– entrada: vetor vet com n elementos elemento elem
– saída: n se o elemento elem ocorre em vet[n]
-1 se o elemento não se encontra no vetor

01/04/2014

(c) Dept. Informática - PUC-Rio

3

Busca Linear em Vetor
• percorra o vetor vet, elemento a elemento, verificando se elem é igual a um dos elementos de vet int busca (int n, int* vet, int elem)‫‏‬
{
int i; for (i=0; i<n; i++) { if (elem == vet[i])‫‏‬ return i; /* encontrou */
}
/* não encontrou */ return -1;
}
01/04/2014

(c) Dept. Informática - PUC-Rio

4

Análise da Busca Linear em Vetor
• pior caso:
– n comparações, onde n representa o número de elementos do vetor • desempenho computacional varia linearmente em relação ao tamanho do problema (algoritmo de busca linear)

– complexidade: O(n)‫‏‬

• caso médio:
– n/2 comparações
• desempenho computacional continua variando linearmente em relação ao tamanho do problema

– complexidade: O(n)‫‏‬

01/04/2014

(c) Dept. Informática - PUC-Rio

5

Busca Linear em Vetor Ordenado
0

1

1

1

2

3

4

int busca_ord (int n, int* vet, int elem)‫‏‬
{
int i; for (i=0; i<n; i++) { if (elem == vet[i])‫‏‬ return i; /* encontrou */ else if (elem < vet[i])‫‏‬ return -1;/* interrompe busca */
}

5

7

8

6

/* não encontrou */ return -1;
}
01/04/2014

(c) Dept. Informática - PUC-Rio

6

Análise da Busca Linear em Vetor Ordenado
• caso o elemento procurado não pertença ao vetor, a busca linear com vetor ordenado apresenta um desempenho ligeiramente superior à busca linear
• pior caso:
– algoritmo continua sendo linear
– complexidade: O(n)‫‏‬

01/04/2014

(c) Dept. Informática - PUC-Rio

7

Busca Binária em Vetor Ordenado
• entrada:

vetor vet com n elementos, ordenado elemento elem

• saída:

n
-1

se o elemento elem ocorre em vet[n] se o