Searching Algorithms
Overzicht
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.
Doelstellingen
- 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.
Mindmap
Dit onderwerp is in kaart gebracht zodat je ziet hoe de ideeen samenhangen.
Open de mindmap in de app
Lesnotitie
Volledige lesnotitie beschikbaar in de Green Bridge-app
Installeer de Green Bridge CBT-app op je telefoon of computer voor de volledige IGCSE-bibliotheek: examens uit voorgaande jaren, correctiemodellen, mindmaps, flashcards en audiolessen.
Lesevaluatie
Gefeliciteerd met het voltooien van de les op Searching Algorithms. Nu je de sleutelconcepten en ideeën, het is tijd om uw kennis op de proef te stellen. Deze sectie biedt een verscheidenheid aan oefeningen vragen die bedoeld zijn om uw begrip te vergroten en u te helpen uw begrip van de stof te peilen.
Je zult een mix van vraagtypen tegenkomen, waaronder meerkeuzevragen, korte antwoordvragen en essayvragen. Elke vraag is zorgvuldig samengesteld om verschillende aspecten van je kennis en kritisch denkvermogen te beoordelen.
Gebruik dit evaluatiegedeelte als een kans om je begrip van het onderwerp te versterken en om gebieden te identificeren waar je mogelijk extra studie nodig hebt. Laat je niet ontmoedigen door eventuele uitdagingen die je tegenkomt; beschouw ze in plaats daarvan als kansen voor groei en verbetering.
- 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
Maak deze vragen in de app
Maak deze vragen in de app
Aanbevolen Boeken
Oefen Proefexamenvragen
Wilt u proefexamenvragen over Searching Algorithms oefenen? Download de Green Bridge CBT-app voor toegang tot proefexamenvragen en volledige oefentoetsen over dit onderwerp.
Download de app in de Google Playstore
Alles wat je nodig hebt om uit te blinken in JAMB, WAEC en NECO.
