Tópicos / GCSE / Computer Science / Algorithms Searching algorithms: linear and binary search Aprenda jogando
Responda a estas perguntas para ganhar energia, depois pesque e explore. Sem precisar de conta.
JOGAR ESTE TÓPICO — GRÁTIS
Para educadores: slides de aula, resumos de revisão prontos para usar de Searching algorithms: linear and binary search (Computer Science, Algorithms) — use na sua aula ou rode o tópico como atividade interativa de turma que seus aprendizes jogam como um jogo ao vivo.
Notas de aula Linear search A linear search checks each item in a list one by one from the start until it finds the target or reaches the end. It works on unsorted or sorted data, and is simple. In the worst case every item is checked, so the time grows with the list size. Linear search Binary search A binary search works only on sorted data. It looks at the middle item : if it equals the target, done; if the target is smaller, discard the upper half; if larger, discard the lower half. Repeat on the remaining half. It is much faster for large lists because it halves the search area each time. For 1,000 items it needs at most about 10 comparisons. Maintain low and high index bounds. If the target is not found and low becomes greater than high, report not found. State how the middle position is rounded when the range has an even number of items. Binary search Comparing For n items, linear search needs up to n target-versus-item checks; binary search repeatedly halves a sorted range. Both can succeed on their first check, so compare worst cases rather than claiming binary is always faster. Comparing search performance Tracing a binary search List: 2, 5, 8, 12, 16, 23, 38. Target 23: middle = 12 (4th) → target larger → right half: 16, 23, 38 → middle 23 → found. Choosing Use binary search for large sorted lists; linear search for small or unsorted lists. Slides Sign up free to view the lesson slides
Step through every slide for this topic — plus flashcards and revision notes — with a free account.
Questões de prática Prévia grátis — 8 de 33 perguntas. Cadastre-se para ver todas. 1. What is a search algorithm?
Easy A a method of finding an item in a listB a way of sortingC a type of loopD a database2. What does a linear search do?
Easy A checks items one by oneB checks the middleC sorts the listD compresses data3. What must be true for binary search?
Easy A the list is sortedB the list is unsortedC the list is shortD the list is numeric only4. What does binary search check first?
Easy A the middle itemB the first itemC the last itemD a random item5. Which search is simpler to program?
Easy A linearB binaryC both equalD neither6. A list is 3, 7, 9, 14, 20. Linear search for 14 takes how many comparisons?
Easy 7. A list is 3, 7, 9, 14, 20. Binary search for 14: what is the first item checked?
Easy 8. After checking 9 for target 14 in the list 3, 7, 9, 14, 20, which items remain?
Easy A 14 and 20B 3 and 7C 7 and 9D 9 onlyMais perguntas 9. What is the worst case for linear search?
Easy A the item is last or missingB the item is firstC the item is in the middleD the list is sorted10. For a non-empty list, which situation needs the fewest comparisons in a linear search?
Easy A the item is firstB the item is lastC the item is missingD the list is empty11. Why can binary search not be used on an unsorted list?
Easy A it relies on order to discard halfB it is slowC it uses a loopD it needs a database12. For one million items already sorted in ascending order, which search has the lower worst-case number of item comparisons?
Medium A binary searchB linear searchC they are the sameD neither works13. In a binary search, the target is smaller than the middle item. What happens?
Medium A the upper half is discardedB the lower half is discardedC the list is sortedD the search ends14. Using one target-versus-middle check per step, what is the maximum number of checks in binary search of 8 sorted items?
Medium 15. When might linear search be better?
Medium A a small or unsorted listB a huge sorted listC a sorted databaseD never16. What is the middle item of 2, 4, 6, 8, 10?
Medium 17. What does a binary search return if the item is not found?
Medium A not found after the list is exhaustedB an error alwaysC the middle itemD the first item18. A list of 7 sorted items: 2, 5, 8, 12, 16, 23, 38. Binary search for 38. What is checked first?
Medium 19. Binary search is finding 38 in the sorted list 2, 5, 8, 12, 16, 23, 38. After checking 12, which item is checked next?
Medium 20. Why might sorting first to use binary search not always be worthwhile?
Medium A the sorting cost may exceed the searching savedB sorting is freeC binary search needs no sortingD linear search is always faster21. How does the worst-case number of item comparisons in linear search grow with list size?
Medium A in direct proportionB not at allC by halvingD randomly22. What is 'efficiency' in an algorithm?
Easy A how few resources such as time it usesB how long the code isC how colourfulD how old23. What does 'midpoint' mean in binary search?
Easy A the middle positionB the first positionC the lastD a random one24. What is needed to keep track of in binary search?
Medium A the low and high positionsB the colourC the fontD the date25. Which search might be used to find a name in a short unsorted list?
Medium A linear searchB binary searchC merge sortD bubble sort26. A linear search checks items one at a time.
Easy True or false?
27. A binary search needs a sorted list.
Easy True or false?
28. In the worst case, linear search needs fewer item comparisons than binary search on a large sorted list.
Easy True or false?
29. Binary search halves the search area each step.
Easy True or false?
30. Binary search works on any unsorted list.
Medium True or false?
31. Which are true of binary search?
Medium A requires sorted dataB checks the middle itemC halves the listD works well on large listsE works only on unsorted lists32. Which are true of linear search?
Medium A simpleB works on unsorted dataC checks items in orderD worst-case comparisons grow directly with list lengthE needs sorted data33. Explain why binary search is more efficient than linear search for large sorted lists.
Medium Unlock all 33 questions & more Crie uma conta grátis para ver todas as perguntas, os slides, flashcards e resumos de revisão deste tópico.
Provas anteriores A prática com provas anteriores deste tópico chega em breve. 
