I thoroughly enjoyed the treatment given to this problem by Jon Bentley.
In particular, the section on “Principles” was such an exciting read – it shows some of the tricks used in algorithm design :
- Save state to avoid recomputation
- Preprocess state into data structures
- Divide and conquer algorithms
- Scanning algorithms
- Cumulatives
- Lower bounds
- Sorting (my humble addition to the list)
References: