Coding interview 的 Sorting & Searching cheatsheet

Sorting/Searching 学习指南，包含练习题、技巧、时间复杂度与推荐资源

Introduction

Sorting 是把序列按数值或字典序排序，且可升序或降序。

很多基础排序算法是 O(n²)，面试中不建议手写。实际面试里，你通常用语言自带的排序函数，然后基于排序结果做 binary search。

在 sorted array 上，利用有序性可以用 binary search，把查找从 O(n) 降到 O(log n)。binary search 通过比较中间元素来决定向左还是向右，直到找到目标或区间为空。