课程名称：JavaScript版数据结构与算法
课程章节：第12章 算法设计思想之“分而治之”
主讲老师：lewis
课程内容：
今天学习的内容包括：
12-1 分而治之简介——分解合解题方法。
12-2 LeetCode：374. 猜数字大小——二分搜索也是分而治之。
课程收获：
分而治之简介
分而治之是什么？
- 分而治之是算法设计中的一种方法。
- 它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题。
场景一：归并排序
- 分:把数组从中间一分为二。
- 解:递归地对两个子数组进行归并排序。
- 合：合并有序子数组。
场景二：快速排序
- 分:选基准，按基准把数组分成两个子数组。
- 解:递归地对两个子数组进行快速排序。
- 合：对两个子数组进行合并。
374. 猜数字大小
解题思路
- 二分搜索，同样具备 “分、解、合” 的特性。
- 考虑选择分而治之。
解题步骤
- 分:计算中间元素，分割数组。
- 解:递归地在较大或者较小子数组进行二分搜索。
- 合:不需要此步，因为在子数组中搜到就返回了。
时间，空间复杂度分析
- 时间复杂度：O(logN)。
- 空间复杂度：O(logN)。
- 一般写二分搜索使用while，一般不使用递归。
今天学习了 分而治之的概念，使用二分搜索进行猜数字大小，为了理解分而治之的理念，在这里使用了递归，没有While版本的空间复杂度好，一般使用While。对自己说一句，加油😀~
坚持打卡，坚持学习！明天见💪~