Pitfalls and Cheat Sheet

Main pitfall

Using binary search on an unsorted list. The algorithm assumes order. If the list is not sorted, it can say "not found" when the value is there, or give a wrong answer. Always use linear search on unsorted data, or sort first and then use binary.

Cheat sheet

• Linear search: Works on any list. Check one by one. Best O(1), worst O(n).
• Binary search: Sorted list only. Cut in half each time. Best O(1), worst O(log n).
• Linked list: Use linear search only; you cannot jump to the middle.