Complexidade do tempo de pesquisa binária

A pesquisa binária é um paradigma de divisão e conquista. Ele procura um item em uma matriz classificada. Neste artigo, apenas a ascensão de classificação é considerada. O item a ser pesquisado é chamado de valor alvo. O valor alvo pode ou não ser encontrado na matriz.

A pesquisa começa comparando o valor alvo com o item do meio da matriz classificada. Se o número de itens na matriz for par, então o item na metade do número é considerado o item do meio. Se o valor alvo for o mesmo que o item do meio, o índice de valor alvo foi encontrado. Se eles não forem iguais, o valor alvo é maior ou menor que o item do meio. Se for maior, a metade inferior da matriz será abandonada para que a busca continue na metade superior. Se for menor, a metade superior da matriz será abandonada, para que a busca continue na metade inferior.

A pesquisa continua dividindo a metade escolhida em dois novamente. Uma comparação entre o valor alvo e o item do meio desta nova metade é feita. Se eles não forem iguais, essa metade é dividida novamente em dois e pelas mesmas razões que a metade anterior foi dividida. Se o valor alvo não for o mesmo que o novo item do meio, a divisão continuar.

Quando o valor alvo e um valor mediano (item) são os mesmos, isso é conquistado. Lá e então, a pesquisa para. Se o valor alvo não estiver na matriz, a pesquisa será interrompida em algum item do meio final, que não é igual ao valor alvo.

Este artigo tem como objetivo dar uma apreciação chamada complexidade do tempo pela velocidade da pesquisa binária.

Conteúdo do artigo

• Introdução - Veja acima
• Ilustração de pesquisa binária
• Complexidade do tempo e pesquisa binária
• Codificação em c
• Conclusão

Ilustração de pesquisa binária

Considere a lista classificada:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Onde o número inteiro, 3, deve ser pesquisado. Obviamente, a pesquisa desde o início levará três operações. No entanto, o uso de pesquisa binária levará quatro operações principais da seguinte forma:

O valor alvo é 3. Dividir a lista em dois faz 8 o item do meio.

É 8 o mesmo que 3?

Não. Como 3 é menor que 8, a pesquisa se concentrará na metade inferior. Essa é uma operação principal feita.

Dividir em dois faz com que 4 o novo item do meio.

É 4 o mesmo que 3?

Não. Como 3 é menor que 4, a pesquisa se concentrará na nova metade inferior. Essa é a segunda operação principal feita.

Dividir -se em dois novamente faz 2 o novo item do meio.

É 2 o mesmo que 3?

Não. Como 3 é maior que 2, a pesquisa se concentrará na nova metade superior. Essa é a terceira operação principal feita.

Dividir em dois novamente faz 3 o novo item do meio, de meia (sub-lista) de comprimento, um. O novo e último item do meio agora é 3.

É 3 o mesmo que 3?

Sim. O valor alvo foi encontrado. Essa é a quarta e a última operação principal feita.

Quando há 16 itens, no máximo 4 operações principais podem ser feitas. Se houvesse 16 itens, e o valor alvo estava no intervalo e não foi possível encontrar, 4 operações principais ainda teriam ocorrido. Por exemplo, na lista a seguir:

1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

Ainda existem 16 itens. Um valor alvo de 3 teria terminado no valor de 5, com 4 operações principais.

Complexidade do tempo e pesquisa binária

Pior desempenho

O desempenho do pior caso refere-se ao caso em que o valor alvo é encontrado na última operação principal, ou o valor alvo está no intervalo de valores e não é encontrado na última operação principal.

Quando o número de itens é 16, o número máximo de operações sempre será 4.

16 = 2⁴
4 = log₂(16)

Seja n 16. Então,

4 = log₂(n)

Se n for 8, o número máximo de operações seria 3 = log₂(8). Se n for 32, o número máximo de operações seria 5 = log₂(32).

Diz-se que a complexidade do tempo no pior caso (velocidade relativa) para pesquisa binária é:

O (log₂(n))

Onde o grande O e seus parênteses tendo log₂(n) é a notação para a complexidade do tempo. Está simplesmente escrito como:

O (log n)

Melhor desempenho

Suponha que o valor alvo foi 8 para a primeira lista acima. Nesse caso, a primeira operação principal teria encontrado a posição do valor alvo. Este é o melhor desempenho. A complexidade do tempo para esse melhor desempenho é escrita como:

O (1)

Onde 1 significa uma operação principal.

Codificação em c

Uma função de pesquisa binária de código C é:

#incluir
int binarySearch (int arr [], int alvo, int n)
int loindex = 0;
int uPIndex = n - 1;
// verifique se ainda temos itens na lista para pesquisar
while (alvo loindex)
upIndex = MiddleIndx;
outro
loindex = MiddleIndx + 1;


// retorna um número negativo quando não conseguirmos encontrar o alvo na matriz
retornar -1;

O loindex significa o menor índice de meia (sub-lista). O upindex significa o índice superior de meia (sub-lista). No começo, Loindex é 0 e upIndex é 15 quando n é 16. A condição do loop enquanto garante que a divisão continue até que Loindex seja o mesmo que upIndex se o valor do alvo ainda não foi encontrado.

Uma função principal C adequada para este código é:

int main (int argc, char ** argv)

int n = 16;
int alvo = 3;
int arr [] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14, 15, 16;
int indexFound = binarySearch (arr, alvo, n);
printf ("%d \ n", indexFound);
retornar 0;

Conclusão

Este artigo discutiu a complexidade do tempo de pesquisa binária e enfatizou o seguinte:

A pior complexidade do tempo para pesquisa binária é:
O (log n)

A melhor complexidade do tempo para pesquisa binária é:
O (1)