Entendendo busca binária

Introdução ao conceito de busca sequencial e binária 08 de julho de 2022
Algoritmos de Busca Busca Binária

Busca sequencial

Problema?

Determinar se um dado número está ou não em um dado vetor ordenado.

Exemplo

Vamos percorrer o vetor posição a posição verificando se o elemento está ou não presente.

2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10Text is not SVG - cannot display

Vamos buscar o elemento 20.

2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
2 == 20 ? Não
2 == 20 ? NãoText is not SVG - cannot display
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
4 == 20 ? Não
4 == 20 ? NãoText is not SVG - cannot display
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
5 == 20 ? Não
5 == 20 ? NãoText is not SVG - cannot display
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
7 == 20 ? Não
7 == 20 ? NãoText is not SVG - cannot display
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
10 == 20 ? Não
10 == 20 ? NãoText is not SVG - cannot display
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
12 == 20 ? Não
12 == 20 ? NãoText is not SVG - cannot display
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
18 == 20 ? Não
18 == 20 ? NãoText is not SVG - cannot display
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
20 == 20 ? Sim
20 == 20 ? SimText is not SVG - cannot display

Elemento 20 encontrado após 8 iterações.

  • E se o elemento não estivesse no vetor?
    • 11 iterações.
  • E se o vetor possuir 1024 elementos?
    • Até 1024 iterações.

n elementos → n iterações

Busca Binária

Problema?

Não aproveitamos o fato do vetor estar ordenado.

Exemplo

Vamos utilizar a estratégia de busca de palavras em um dicionário.

Acha-se o elemento do meio do vetor e compara-se com o elemento a ser buscado. Em seguida decidimos se a procura continua para a esquerda ou para a direita, até que não existam mais elementos a ser comparados.

2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10Text is not SVG - cannot display

Vamos buscar o elemento 20 novamente.

Elemento do meio:

  • Índice da primeira posição do vetor onde o elemento será buscado: e
  • Índice da última posição do vetor onde o elemento será buscado: d
  • Elemento do meio: m = (e + d)/2
    • m = (0 + 10)/2 = 5
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
12 == 20 ? Não
12 == 20 ? NãoText is not SVG - cannot display
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
12 < 20 ? Sim
12 < 20 ? SimText is not SVG - cannot display

Podemos descartar todos os elementos à esquerda do 12 e o próprio 12.

Repete-se a idéia para o restante do vetor:

  • Elemento do meio = (6 + 10)/2 = 8
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
21 == 20 ? Não
21 == 20 ? NãoText is not SVG - cannot display
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
21 < 20 ? Não
21 < 20 ? NãoText is not SVG - cannot display

Podemos descartar todos os elementos à direita do 21 e o próprio 21.

Repete-se a idéia para o restante do vetor:

  • Elemento do meio = (6 + 7)/2 = 6
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
18 == 20 ? Não
18 == 20 ? NãoText is not SVG - cannot display
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
18 < 20 ? Sim
18 < 20 ? SimText is not SVG - cannot display

Podemos descartar todos os elementos à esquerda do 18 e o próprio 18.

Repete-se a idéia para o restante do vetor:

  • Elemento do meio = (7 + 7)/2 = 7
2
2
4
4
5
5
7
7
10
10
12
12
18
18
20
20
21
21
22
22
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
28
28
10
10
20 == 20 ? Sim
20 == 20 ? SimText is not SVG - cannot display

Elemento 20 encontrado após 4 iterações.

  • E se o elemento não estivesse no vetor?
    • 4 iterações.
  • E se o vetor possuir 1024 elementos?
    • Vamos analisar…

Como calcular o número de iterações no pior caso:

Tamanho do vetor: n

O vetor é dividido por 2 a cada iteração:

1ª iteração: n/2
2ª iteração: (n/2)/2 = n/4
3ª iteração: (n/4)/2 = n/8
...
kª iteração: (n/2k) = 1

k é o número de iterações. Como calcular o valor de k?

(n/2k) = 1
n = 2k
2k = n
k = log2 n

Para n = 1024 → k = 10.
Para n = 1.099.511.627.776 → k = 40

Um grande abraço e até o próximo post!

Compartilhar: Twitter Facebook LinkedIn VK Reddit