Searching algorithms · Algoritmos de busca
| English | Português |
|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | busca linear |
| binary search/ˈbaɪnəri sɜːtʃ/ | busca binária |
Twenty questions for a million names
- A phone book holds a million names. Checking them one at a time, you would expect half a million comparisons before finding the one you want.
- Open it in the middle instead, decide which half the name is in, and throw the other half away. Repeat. You reach any name in twenty comparisons.
- Half a million against twenty is not a small saving; it is the difference between a program that works and one that cannot be used. And it costs one thing: the list must already be in order.
- This lesson is linear search 线性查找 and binary search 二分查找, how each performs, and how to choose.
Vinte perguntas para um milhão de nomes
- Um livro telefônico contém um milhão de nomes. Verificá-los um de cada vez, espera-se meio milhão de comparações antes de encontrar o que se deseja.
- Abra-o ao meio em vez disso, decida qual metade o nome está, e jogue fora a outra metade. Repita. Você chega a qualquer nome em vinte comparações.
- Meio milhão contra vinte não é uma economia pequena; é a diferença entre um programa que funciona e um que não pode ser usado. E custa uma coisa: a lista já deve estar em ordem.
- Esta lição é busca linear 线性查找 e busca binária 二分查找, como cada uma se comporta, e como escolher.
Linear search
- It walks from the start, comparing each element with the target, and stops when it finds a match or reaches the end.
- It works on any list, sorted or not, and on any structure that can be stepped through.
- Worst case: the target is last or absent, so all $n$ elements are compared, which is $O(n)$. On average, about half.
One at a time, from the beginning
Busca linear
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // not found
- Ela percorre do início, comparando cada elemento com o alvo, e para quando encontra uma correspondência ou atinge o fim.
- Funciona em qualquer lista, ordenada ou não, e em qualquer estrutura que possa ser percorrida.
- Pior caso: o alvo está no final ou ausente, então todos $n$ elementos são comparados, o que é $O(n)$. Na média, cerca da metade.
Uma de cada vez, do começo
A linear search: · Uma busca linear:
Linear search needs no preparation and works on any list, at worst O(n). · A busca linear não precisa de preparação e funciona em qualquer lista, no pior caso O(n).
Linear search is the better choice when the data is: · A busca linear é a melhor escolha quando os dados são:
With no order to exploit (or a tiny list), linear search avoids the cost of sorting first. · Sem ordem para explorar (ou uma lista minúscula), a busca linear evita o custo de ordenar primeiro.
Binary search
- It requires the data to be sorted. Compare the middle element with the target: if it matches, stop; if the target is larger, discard the lower half; otherwise discard the upper half.
- Each comparison halves the range still to be searched, so the number of comparisons is $O(\log_2 n)$.
- That is why a million items need about twenty comparisons: $2^{20}$ is just over a million.
Busca binária
low ← 1 ; high ← n
WHILE low <= high DO
mid ← (low + high) DIV 2
IF A[mid] = target THEN
RETURN mid
ENDIF
IF A[mid] < target THEN
low ← mid + 1
ELSE high ← mid - 1
ENDWHILE
RETURN -1
- Requer que os dados estejam ordenados. Compare o elemento do meio com o alvo: se corresponder, pare; se o alvo for maior, descarte a metade inferior; caso contrário, descarte a metade superior.
- Cada comparação mitade a faixa ainda a ser pesquisada, então o número de comparações é $O(\log_2 n)$.
- É por isso que um milhão de itens precisam de cerca de vinte comparações: $2^{20}$ é pouco mais de um milhão.
Searching algorithms · Algoritmos de busca
binary halves the range each step · busca binária reduz o intervalo pela metade a cada passo
Linear search checks every item; binary · binária halves a sorted list — far fewer comparisons. · Linear verifica cada item; binária reduz à metade uma lista ordenada — muito menos comparações.
The worst-case time complexity of binary search is: · A complexidade temporal do pior caso da busca binária é:
Halving the range each step gives a logarithmic number of comparisons. · Reduzir o intervalo pela metade a cada passo resulta em um número logarítmico de comparações.
About how many comparisons does a binary search need for one million sorted items? · Aproximadamente quantas comparações uma busca binária precisa para um milhão de itens ordenados?
$\log_2(1\,000\,000) \approx 20$ — about 20 comparisons. · $\log_2(1\,000\,000) \approx 20$ — cerca de 20 comparações.
Binary search can be used on any list, sorted or not. · A busca binária pode ser usada em qualquer lista, ordenada ou não.
It decides which half to discard by comparing with the middle element, which is only meaningful if the data is in order. · Ela decide qual metade descartar comparando com o elemento do meio, o que só faz sentido se os dados estiverem em ordem.
Binary search is O(log n) because each comparison ____ the range still to be searched. · A busca binária é O(log n) porque cada comparação ____ o intervalo restante a ser pesquisado.
Twenty halvings take a million down to one, which is why 2^20 being just over a million is the number to remember. · Vinte reduções pela metade levam um milhão a um, por isso 2^20 sendo pouco mais de um milhão é o número a lembrar.
Worked example: trace a binary search
- The sorted list is 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Trace the search for 23.
lowis 1,highis 10, somidis 5, holding 16. 16 is less than 23, so discard the lower half:lowbecomes 6.low6,high10, somidis 8, holding 56. 56 is greater than 23, sohighbecomes 7.low6,high7, somidis 6, holding 23. Found, in three comparisons where a linear search would have taken six.- Show
low,high,midand the value at each step. Most of the marks are in the trace, not the answer.
Exemplo resolvido: rastreie uma busca binária
- A lista ordenada é 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Rastreie a busca por 23.
lowé 1,highé 10, entãomidé 5, contendo 16. 16 é menor que 23, então descarte a metade inferior:lowtorna-se 6.low6,high10, entãomidé 8, contendo 56. 56 é maior que 23, entãohightorna-se 7.low6,high7, entãomidé 6, mantendo 23. Found, em três comparações onde uma pesquisa linear teria demorado seis.- Mostre
low,high,mide o valor em cada etapa. A maioria dos pontos está no rastreamento, não na resposta final.
In the sorted list 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, how many comparisons does a binary search need to find 23? · Na lista ordenada 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, quantas comparações uma busca binária precisa para encontrar 23?
mid 5 holds 16 (too small), mid 8 holds 56 (too large), mid 6 holds 23. A linear search would have taken six. · meio 5 contém 16 (muito pequeno), meio 8 contém 56 (muito grande), meio 6 contém 23. Uma busca linear teria levado seis passos.
Choosing between them
| linear | binary | |
|---|---|---|
| data must be sorted | no | yes |
| comparisons, worst case | $n$ | $\log_2 n$ |
| a million items | up to 1,000,000 | about 20 |
| suits | unsorted or small lists, linked lists | large sorted arrays, searched repeatedly |
- Sorting first costs more than one linear search, so binary search pays only when the list is already sorted or will be searched many times.
- Binary search also needs direct access to the middle element, which an array has and a linked list does not.
Escolhendo entre eles
| linear | binária | |
|---|---|---|
| os dados devem estar ordenados | não | sim |
| comparações, caso pior | $n$ | $\log_2 n$ |
| um milhão de itens | até 1,000,000 | cerca de 20 |
| adequa-se a | listas desordenadas ou pequenas, listas ligadas | grandes arrays ordenados, buscados repetidamente |
- Ordenar primeiro custa mais do que uma única busca linear, então a busca binária só vale a pena quando a lista já está ordenada ou será buscada muitas vezes.
- A busca binária também precisa de acesso direto ao elemento do meio, o que um array tem e uma lista ligada não tem.
Worked example: justify the choice
- A program searches an unsorted list of 50 records once. Linear search: sorting the list first would cost far more than the 50 comparisons the search needs.
- A program searches a sorted array of a million records thousands of times a second. Binary search: the data is already sorted and each search costs about 20 comparisons instead of up to a million.
- A program searches a linked list. Linear search: binary search needs to jump straight to the middle element, and a linked list can only be followed from the start.
- Name the algorithm, then the property of the data that decides it.
Exemplo resolvido: justificar a escolha
- Um programa busca uma lista desordenada de 50 registros uma vez. Busca linear: ordenar a lista primeiro custaria muito mais do que as 50 comparações necessárias para a busca.
- Um programa busca um array ordenado de um milhão de registros milhares de vezes por segundo. Busca binária: os dados já estão ordenados e cada busca custa cerca de 20 comparações em vez de até um milhão.
- Um programa busca uma lista ligada. Busca linear: a busca binária precisa pular diretamente para o elemento do meio, e uma lista ligada só pode ser percorrida do início.
- Nomeie o algoritmo, depois a propriedade do dados que o determina.
Match each search to its key facts. · Associe cada busca às suas informações-chave.
Binary search is far faster (O(log n)) but only on sorted data; linear works anywhere at O(n). · A busca binária é muito mais rápida (O(log n)) mas apenas em dados ordenados; a linear funciona em qualquer lugar em O(n).
When is linear search the better choice? Select all · todos that apply. · Quando a busca linear é a melhor escolha? Selecione todas as que se aplicam.
The last case is exactly where binary search wins. Sorting first costs more than a single linear search, so it pays only over many searches. · O último caso é exatamente onde a busca binária vence. Ordenar primeiro custa mais do que uma única busca linear, então compensa apenas sobre muitas buscas.
The cost of keeping the file sorted
- Binary search is only available on a sorted list, and that sorting is not free. A question that asks you to justify a choice is asking you to price it.
- If the data is searched often and changed rarely, sort it once and every later search is $\log_2 n$. That is the case for a dictionary or a lookup table.
- If the data changes constantly, every insertion has to keep the order, which costs a shift of the later elements. A linear search over unsorted data can then be the cheaper total.
- Numbers make the argument concrete: a million records need up to a million comparisons linearly, but only 20 by binary search, since $2^{20} > 10^6$.
- So the marked answer names both halves: how often it is searched, and how often it changes.
O custo de manter o arquivo ordenado
- A busca binária só está disponível em uma lista ordenada, e essa ordenação não é gratuita. Uma questão que pede para você justificar uma escolha está pedindo para avaliar seu custo-benefício.
- Se os dados são buscados com frequência e alterados raramente, ordene-os uma vez e toda busca subsequente será $\log_2 n$. Esse é o caso de um dicionário ou tabela de consulta.
- Se os dados mudam constantemente, cada inserção precisa manter a ordem, o que custa um deslocamento dos elementos subsequentes. Uma busca linear sobre dados desordenados pode então ter o custo total menor.
- Números tornam o argumento concreto: um milhão de registros precisam de até um milhão de comparações na linear, mas apenas 20 na binária, pois $2^{20} > 10^6$.
- Então a resposta marcada nomeia ambas as metades: com que frequência é buscada e com que frequência muda.
Put the justification for choosing a search algorithm in order. · Coloque a justificativa para escolher um algoritmo de busca em ordem.
A justify question wants the trade-off, not the winner. Binary search on a list that changes constantly can cost more in total than a linear search. · Uma questão de justificar quer saber o trade-off, não o vencedor. A busca binária em uma lista que muda constantemente pode custar mais no total do que uma busca linear.
Marks that slip away
- Binary search requires sorted data. Saying "it is faster" without that condition loses the mark.
- Each step halves the range, which is where the $\log_2 n$ comes from. Give the reason, not just the notation.
- Both searches must be able to report not found, which is what the
-1and the loop condition are for. - Binary search needs direct access, so it does not apply to a linked list even if the list is sorted.
Marcas que escapam
- A busca binária requer dados ordenados. Dizer "é mais rápida" sem essa condição faz perder o ponto.
- Cada etapa reduz pela metade o intervalo, que é de onde vem o $\log_2 n$. Dê o motivo, não apenas a notação.
- Ambas as buscas devem ser capazes de relatar não encontrado, que é para que servem o
-1e a condição do loop. - A busca binária precisa de acesso direto, então não se aplica a uma lista ligada mesmo que a lista esteja ordenada.
You've got it
- linear search compares each element from the start, works on any list, and is $O(n)$
- binary search needs sorted data with direct access, compares the middle and halves the range each time, giving $O(\log_2 n)$: about 20 comparisons for a million items
- trace a binary search by showing
low,high,midand the value at each step - choose from the data: unsorted, small or a linked list means linear; large, sorted and searched often means binary
Entendeu?
- busca linear compara cada elemento do início, funciona em qualquer lista, e é $O(n)$
- busca binária precisa de dados ordenados com acesso direto, compara o meio e reduz pela metade o intervalo a cada vez, dando $O(\log_2 n)$: cerca de 20 comparações para um milhão de itens
- rastreie uma busca binária mostrando
low,high,mide o valor em cada etapa - escolha entre os dados: desordenado, pequeno ou uma lista ligada significa linear; grande, ordenado e buscado frequentemente significa binária