数据结构与算法 - 07 二分搜索与贪婪
- 二分搜索 Binary Search
- 定义
- 又叫 折半搜索
- 在有序数组中查找某一特定元素的搜索算法
- 前提：数组必须有序
- 优点
- 时间复杂度：O(lgn)，非常高效
- 又叫 对数搜索
- 缺点
- 要求待查找的数组或区间是排好序的
- 应用
- 数据是排好序的，且不会经常变动
- 代码
- 递归
- 非递归
- 递归
- 定义
- 贪婪 Greedy
- 定义
- 每一步都采用在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法
- 优点
- 从局部考虑问题，而非整体
- 当局部最优解 能产生 全局最优解时，才能用
- 缺点
- 并不是所有问题都能用它解决
- 得到的结果并不一定是正确的
- 【因这种算法容易过早地做出决定，从而没办法达到最优解】
- 应用
- 当局部最优解 能产生 全局最优解时，才能用
- 练习
- LC253：会议室Ⅱ，给定一系列会议的起始时间和结束时间，求最少需要多少个会议室可以让这些会议顺利召开
- 思路：
- 将会议按照起始时间排序
- 给新的即将开始的会议，找会议室时，先看当前有无空会议室
- 有则在空会议室开会，无 则开设一间新会议室
- 定义