BINARY SEARCH BUSCA BINÁRIA
Time Complexity Complexidade de Tempo
A binary search can only be made in a sorted array. It is a very efficient search algorithm which consists of truncating the array in half every time an element is checked against the searched element to see if they match. Uma busca binária só pode ser feita numa lista ordenada. É um algoritmo de busca muito eficiente que consiste em dividir a lista a meio de cada vez que um elemento é comparado com o elemento que procuramos, para ver se coincidem.
This means that, in mathematical terms, this search is conducted in log2(n) time, or O(log2(n)) time, in what's known as Big-O notation. This notation is used to express how efficient an algorithm is. It can relate to time, or space efficiency, but here we're only going to talk about time. And in the case of binary searches, only logarithmic time. Isto significa que, em termos matemáticos, esta busca é levada a cabo em tempo log2(n), ou tempo O(log2(n)), nesta notação conhecida como notação O-grande. Esta notação é usada para exprimir quão eficiente é um algoritmo. Pode referir-se a eficiência de tempo ou de espaço, mas aqui vamos falar apenas de tempo. No caso de buscas binárias, de tempo logarítmico.
This may look scary, but don't panic. We can boil it down to this: Tudo isto pode parecer assustador, mas não entres em pânico. Podemos resumir tudo ao seguinte:
=> n is the length of the array, list, set, etc. that's being searched. If the array has 20 elements in it, n is 20. => n é o tamanho da lista sobre a qual conduzimos a busca. Se a lista tem 20 elementos, n é 20.
=> log2 means logarithm of base 2. We use base 10 in our everyday lives, but in this case, since we're dividing a list in two at each step (binary search) until we find what we're looking for, it makes sense that the base we work with is 2. => log2 significa logaritmo de base 2. No nosso dia-a-dia usamos base 10, mas, neste caso, como estamos a dividir uma lista em dois a cada passo (busca binária) até descobrirmos o elemento que procuramos, faz sentido que a base usada seja 2.
So how do we find log2(n)? What even is this? Então como é que descobrimos log2(n)? O que é isto, afinal?
A logarithm is the opposite of an exponent. The higher n is, the less log(n) increases. If it were an exponent, it would increase exponentially. For example, 22 => 4, but 42 => 16, while log2(4) => 2 and log2(8) => 3. In the first case, the result of the second iteration increased to a factor of four of the exponentiated number (4=>16), but in the second one, only to 1.5 (2=>3). Since it's a logarithm, it increases logarithmically. Um logaritmo é o oposto de um expoente. Quanto maior for n, mais devagar log(n) aumenta. Se se tratasse de um expoente, este aumentaria exponencialmente. Por exemplo, 22 => 4, mas 42 => 16, enquanto que log2(4) => 2 e log2(8) => 3. No primeiro caso, o resultado da segunda iteração aumentou quatro vezes (4=>16), mas, no segundo, só 1,5 (2=>3). Uma vez que se trata de um logaritmo, aumenta logaritmicamente.
log2(n) is going to be the number of steps it will take us to find what we're looking for. Think of it as "guessing". The machine can't look at an array and just "see" what it's looking for. It has to check an element and painstakingly compare it to the one that's being searched, to see if they're the same. It falls on us to tell it which elements it's going to check, and that's where this binary search algorithm comes into play. log2(n) será o número de passos, ou etapas, que temos pela frente até encontrarmos o que procuramos. Pensa nisto como "adivinhar". A máquina não consegue olhar para uma lista e "ver" o que procura. Precisa de pegar num certo elemento e compará-lo meticulosamente com o que está a ser procurado, para ver se são iguais. Cabe-nos a nós dizer-lhe que elementos é que vai verificar e é aí que este algoritmo de busca binária entra em jogo.
In order to find log2(n), we just need to find out how many times we need to divide n to get to 1. We want to go from a list of n elements to just one by cutting it in half each time. In other words, to what power do we need to elevate the base (2) in order to reach n? De modo a encontrarmos log2(n), só precisamos de descobrir quantas vezes precisamos de dividir n para chegar a 1. Queremos ir de uma lista de n elementos até apenas um elemento, dividindo-a ao meio a cada passo. Noutras palavras, a que potência é que precisamos de elevar a base (2) para alcançarmos n?
Let's say n = 16. Digamos que n = 16.
What must we power our base (of 2) by in order to get n, or 16? Or how many times do we have to divide n by 2, to get 1? Let's try it: A que potência devemos elevar a nossa base (2) para chegar a n? Ou quantas vezes devemos dividir n por 2, para obter 1? Vamos tentar:
16 / 2 = 8 | One step 16 / 2 = 8 | Um passo
8 / 2 = 4 | Two steps 8 / 2 = 4 | Dois passos
4 / 2 = 2 | Three steps 4 / 2 = 2 | Três passos
2 / 2 = 1 | Four steps 2 / 2 = 1 | Quatro passos
Therefore, log2(16) = 4, because 24 is 16. It took us four steps to reach 1. 1 is the number of elements we want to reach in our search. We're not searching for 16, or 8, or 4 elements. We're looking for a particular one. Portanto, log2(16) = 4, porque 24 é 16. Necessitámos de quatro passos para alcançar 1. 1 é o número de elementos que queremos alcançar na nossa busca. Não estamos à procura de 16, ou 8, ou 4 elementos. Estamos à procura de um em específico.
So this is how we know a binary search's time complexity. If the division yields a number with decimal places, we just round it. Now, to see it in action. É assim que sabemos a complexidade de tempo de uma busca binária. Se uma divisão der um resultado com casas decimais, arredondamos. Agora vamos vê-la em acção.