1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
---
category: Algorithms & Data Structures
name: Binary Search
contributors:
- ["Abhishek Jaisingh", "http://github.com/abhishekjiitr"]
translators:
- ["Claudson Martins", "https://github.com/claudsonm"]
lang: pt-br
---
# Busca Binária
## Por Que Busca Binária?
Operações de busca são um dos principais problemas na Ciência da Computação.
Atualmente existem mais de 1 trilhão de buscas por ano, e nós precisamos de
algoritmos que possam realizá-las rapidamente. Busca binária é um dos algoritmos
fundamentais em ciência da computação. A fim de explorá-la, iremos primeiro
construir um conhecimento teórico, e então utilizá-lo para implementar o
algoritmo apropriadamente.
## Introdução
Uma abordagem simples para implementar uma busca é realizar uma busca linear,
mas algoritmos nessa abordagem levam muito tempo, o qual cresce linearmente de
acordo com a quantidade ou número de dados. Por exemplo, iniciando do elemento
mais a esquerda de arr[] e um a um comparar x com cada elemento de arr[], se x
coincide com um elemento, retornar seu índice. Se x não coincide com nenhum dos
elementos, retornar -1.
```
Busca Linear: O (n) Tempo Linear
Busca Binária: O ( log(n) ) Tempo Logarítmico
```
```
def busca(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
```
## Algoritmo de Busca Binária
O pré-requisito básico para que uma busca binária funcione é que os dados que se
desejam buscar devem estar ordenados (em qualquer ordem).
### Pseudocódigo
```
A ideia da busca binária é usar a informação de que o array está ordenado e
reduzir a complexidade de tempo para O(Log n). Nós basicamente ignoramos metade
dos elementos após uma comparação.
1) Compare x com o elemento do meio.
2) Se x coincide com o elemento do meio, retorne o índice do meio.
3) Senão Se x é maior que o elemento do meio, então x só pode estar no lado
direito do elemento do meio. Portanto nós pulamos para a metade direita.
4) Senão (x é menor) pulamos para a metade esquerda.
Essa é a ideia da implementação recursiva da busca binária.
```
### Considerações Finais
Existem outras formas de busca binária que são muito úteis.
## Recursos Online
* [GeeksforGeeks](http://www.geeksforgeeks.org/the-ubiquitous-binary-search-set-1/)
* [Topcoder Tutorial](https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/)
|
