busca linear e binaria

O que é busca linear?
Do ingles linear search, é um mecanismo de busca no qual percorre um vetor até encontrar o valor passado como parâmetro, retornando assim o índice do valor encontrado.

Complexidade da busca linear: O(n)

O que é a busca binária?
Do inglês binary search, é um mecanismo de busca no qual espera um vetor ordenado e um valor para ser identificado dentro do vetor, a partir daí é feita a busca e retorna o índice do valor que está dentro do vetor

Como funciona?

Busca linear

Imagine que você tem o seguinte vetor:
2 3 6 7 8 10 14 17 18

Você quer achar o índice do valor 10.

Agora, você percorre desde o primeiro até achar o valor, senão é retornado -1 para dizer que busca não obteve sucesso.

Exemplificando, percorrendo um por um:

indice = 0.

2 = 10? não. indice = indice + 1 (igual a 1)

2 3 6 7 8 10 14 17 18
3 = 10? não. indice = indice + 1 (igual a 2)

2 3 6 7 8 10 14 17 18

6 = 10? não. indice = indice + 1 (igual a 3)

2 3 6 7 8 10 14 17 18
7 = 10? não. indice = indice + 1 (igual a 4)

2 3 6 7 8 10 14 17 18
8 = 10? não. indice = indice + 1 (igual a 5)

2 3 6 7 8 10 14 17 18
10 = 10? sim. retorna indice (igual a 5)

2 3 6 7 8 10 14 17 18

Busca binária

Imagine que você tem um vetor de tamanho 9, com números ordenados.

vetor = 2 3 6 7 8 10 14 17 18

Você vai comparar o valor passado por parâmetro com o valor do meio do vetor.
Agora, você quer saber onde está um valor (o índice do valor) dentro desse vetor.
Digamos que você quer saber o índice do número 17.

No caso:

valor = 17

8 < 17? sim

Então, eu só preciso focar minha busca do meio para o fim.

2 3 6 7 8 10 14 17 18

Agora, a mesma coisa, a partir do lado do vetor que o valor pode estar pegando o valor do meio, ou um meio aproximado.

14 < 17? sim

2 3 6 7 8 10 14 17 18

17 < 17? não
17 > 17? não

2 3 6 7 8 10 14 17 18

Então achamos o valor.

retorna 7.

Pode ser implementado da seguinte forma:

1
2
3
4
5