MediumPython ProgrammingHigh School (9–10)High School (11–12)UndergraduateGeneralPython Essentials › Searching and SortingConceptualPython-CodedBoard ExamAPA-LevelIB
Which search would you use? (a) A list of 5 names in no particular order…
Contributed by StemPy LabTry it on paper first. A hint, the key idea and the worked solution are here when you need them.
Which search would you use? (a) A list of names in no particular order. (b) A sorted list of numbers. (c) A list of numbers that is not sorted, searched only once. How many checks does the binary search need at most for , , and items?
Need a reminder? The key ideaShow
Binary search needs a sorted list. Sorting costs time, so it pays off when you search many times.
The worked solution
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, compare your working with the solution.
- (a) Linear search. The list is short, and it is not sorted.
- (b) Binary search. The list is long and it is sorted, so halving saves a great deal of work.
- (c) Linear search. Sorting 50 numbers first costs more than a single linear search.
The most checks for binary search: , , and .
Discussion (0)
Log in to join the discussion.
Loading…