Internship← Competitive Programming learning pathCompetitive Programming · Module 4 of 10
Sorting, searching and two pointers
Classic tools that turn O(n^2) ideas into O(n log n) or O(n).
📖 Key ideas
- Sort first: many problems become simple on sorted data.
- Binary search finds a value or a boundary in O(log n).
- Binary search on the answer: test "is x feasible?" and halve the range.
- Two pointers move through a sorted array from both ends or together.
- Sliding window keeps a running range for subarray problems.
💡 Real-life example: Two pointers are two people searching a sorted bookshelf from both ends until they meet.
Binary searchHalve the search range each step
Two pointersTwo indexes moving through an array
Sliding windowMoving range over a subarray
lower_boundFirst position not less than a value