Searching Algorithms
Visão Geral
You have lost your passport somewhere in the house. One way to find it is to start in the hall and search every room in turn until you hit it. The other way, if the house is a hotel with numbered rooms and you know the number, is to walk to the middle corridor, see whether your room is above or below, and ignore half the building. Both plans find the passport. Only one of them is any use in a hotel with a thousand rooms.
Those two plans are the linear search and the binary search, and this specification wants three things from you: the mechanics of each, the ability to follow and write pseudocode for both, and a clear-eyed comparison of where each one wins. The comparison is not simply that binary is faster. Binary search demands something in return, and knowing what it demands is the difference between a two-mark answer and a four-mark one.
Objetivos
- Understand and explain how the linear search algorithm works.
- Understand and explain how the binary search algorithm works.
- Compare and contrast linear and binary search algorithms.
Mapa mental
Este tema esta mapeado para mostrar como as ideias se ligam.
Abra o mapa mental na aplicacao
Nota de Aula
Apontamento completo disponivel na aplicacao Green Bridge
Instale a aplicacao Green Bridge CBT no telemovel ou computador para aceder a biblioteca IGCSE completa: exames anteriores, criterios de correcao, mapas mentais, cartoes de estudo e licoes em audio.
Avaliação da Lição
Parabéns por concluir a lição em Searching Algorithms. Agora que você explorou o conceitos e ideias-chave, é hora de colocar seu conhecimento à prova. Esta seção oferece uma variedade de práticas perguntas destinadas a reforçar sua compreensão e ajudá-lo a avaliar sua compreensão do material.
Irá encontrar uma mistura de tipos de perguntas, incluindo perguntas de escolha múltipla, perguntas de resposta curta e perguntas de redação. Cada pergunta é cuidadosamente elaborada para avaliar diferentes aspetos do seu conhecimento e competências de pensamento crítico.
Use esta secção de avaliação como uma oportunidade para reforçar a tua compreensão do tema e identificar quaisquer áreas onde possas precisar de estudo adicional. Não te deixes desencorajar pelos desafios que encontrares; em vez disso, vê-os como oportunidades de crescimento e melhoria.
- Which condition must be met before a binary search can be used? A. The data must be stored in a file B. The data must be numeric C. The data must be sorted D. The data must contain no duplicates Answer: C
- An array holds 64 sorted items. What is the maximum number of comparisons a binary search will make? A. 6 B. 8 C. 32 D. 64 Answer: A
- A linear search is used on an array of 40 items to look for a value that is not present. How many comparisons are made? A. 1 B. 20 C. 39 D. 40 Answer: D
- In an iterative binary search, which assignment is made when the middle element is smaller than the target? A. First becomes Middle B. First becomes Middle + 1 C. Last becomes Middle D. Last becomes Middle - 1 Answer: B
- Which of the following is an advantage of a linear search over a binary search? A. It makes fewer comparisons on large data sets B. It works on data that is not in any order C. It halves the search area at each step D. It can only be used on arrays Answer: B
Resolva estas questoes na aplicacao
Resolva estas questoes na aplicacao
Livros Recomendados
Pratique Questões Simuladas
Quer praticar questões simuladas sobre Searching Algorithms? Descarregue a aplicação Green Bridge CBT para aceder a questões simuladas e avaliações completas sobre este tópico.
Descarregar a aplicação na Google Play Store
Tudo o que precisas para te destacares no JAMB, WAEC e NECO.
