Merge remote-tracking branch 'adambard/master'

1 files changed, 77 insertions, 0 deletions

diff --git a/pt-br/binary-search-pt.html.markdown b/pt-br/binary-search-pt.html.markdown
new file mode 100644
index 00000000..d3060506
--- /dev/null
+++ b/pt-br/binary-search-pt.html.markdown
@@ -0,0 +1,77 @@
+---
+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/)