Ch 6 · Searching — Finding the Needle · Data Structures & Algorithms

Topic 6 of 10 in Data Structures & Algorithms — Foundations — 2 lessons.

Linear Search

The simplest search: look at each item until you find the target. It always works, on any list, but it is O(n) — on average you scan half the list.

Binary Search

If the data is sorted, you can do far better. Look at the middle: if the target is smaller, throw away the right half; if larger, throw away the left. Each step removes half the remaining items — that is O(log n). A million items take only ~20 steps.

All topics in Data Structures & Algorithms Beginner

1. Thinking Like a Computer Scientist
2. Arrays & Lists — The Workhorse
3. Stacks — Last In, First Out
4. Queues — First In, First Out
5. Linked Lists — Nodes on a Chain
6. Searching — Finding the Needle
7. Sorting — Putting Things in Order
8. Recursion — Functions That Call Themselves
9. Hash Tables — Instant Lookups
10. Mini-Projects & Practice