Algoritmos de busca linear e busca binária §

---

Problema da busca em vetores §

Dada uma lista com elementos e um elemento , o problema de busca consistem em verificar se e qual é a primeira ocorrência desse elemento na lista. Onde:

• : são os índices da lista;
• : são os valores da lista;
• é a posição do elemento o qual queremos buscar.

Na linguagem C, existem bibliotecas que possuem funções prontas para buscar elementos em um vetor tais como, lsearch, ifind e bsearch.

Busca linear §

A busca linear, também chamada de busca sequencial, consistem no seguinte algoritmo:

1. Para cada posição do vetor, verifica-se se ela contém o elemento a ser buscado. Caso seja verdadeiro, devolve-se a posição do elemento.
2. Se após percorrer todo o vetor e não for encontrado o elemento, devolve-se um resposta de que o vetor não contém esse elemento, geralmente é retornado -1.

Exemplo §

Suponha o seguinte vetor abaixo e considere que queremos buscar o elemento 6. Agora, vamos executar o algoritmo da busca linear para encontrar esse elemento. Então vamos percorrer todos os elementos do vetor até encontrar o elemento 6 e então retornar a sua posição.

Exemplo em C §

#include <stdio.h>
 
int linear_search(int array[], int size, int element) {
  for (int i = 0; i < size; i++) {
	  if (array[i] == element) {
	      return i;
	  }
  }
  return -1;
}

Busca binária §

Quando a lista está ordenada e não contém elementos repetidos, é possível utilizar uma técnica de divisão e conquista chamada de busca binária. Ela consiste no seguinte algoritmo:

1. Calcular o índice médio e verificar o valor da lista nesta posição.
2. Se o elemento procurado for igual ao valor do meio da lista, então a resposta foi encontrada.
3. Se o elemento procurado for menor que o valor do meio da lista, então, é repetido o procedimento na primeira metade da lista
4. Se o elemento procurado for maior que o valor do meio da lista, então, é repetido o procedimento na segunda metade da lista
5. Caso uma das listas a ser verificada for vazia, então o elemento não foi encontrado.

Exemplo §

Suponha a lista abaixo no qual queremos buscar o elemento 7 usando o algoritmo de busca binária. A partir dessa lista, vamos aplicar o algoritmo de busca binária para encontrar o elemento 7.

Exemplo em C §

int binary_search(int arr[], int l, int r, int x)
{
	while (l <= r) {
		int m = l + (r - l) / 2;
 
		// Check if x is present at mid
		if (arr[m] == x)
			return m;
 
		// If x greater, ignore left half
		if (arr[m] < x)
			l = m + 1;
 
		// If x is smaller, ignore right half
		else
			r = m - 1;
	}
 
	// If we reach here, then element was not present
	return -1;
}

Referências §

---