Intro to Computer Science / Unit 3: Algorithms and Problem Solving
3.5 Searching Algorithms and Efficiency
Notes
Efficiency describes how much time or memory an algorithm needs, often as the input gets larger.
- Linear search checks each item one by one from the start. It works on any list but may check every item.
- Binary search works only on a sorted list. It checks the middle, then throws away half the list each time.
- Example: in a sorted list of 100 items, linear search might need 100 checks, but binary search needs at most 7 (because 2 to the 7th power is 128, which is at least 100).
- Doubling the list size adds just one more step for binary search.
- Two correct algorithms can differ a lot in speed. Choosing the more efficient one matters for big data.
Practice
What is required before you can use binary search on a list?
Binary search relies on order to discard half the items each time.
A list has 1,000 sorted items. About the most checks needed by binary search is:
2 to the 10th power is 1,024, which is at least 1,000, so at most 10 checks.
You are searching an unsorted list of 50 names for one name. Which algorithm can you use?
Binary search needs a sorted list, but linear search works on any list.
Ready for more? Take the Unit 3 test.