读书笔记：《算法漫步》第3章内容总结

问题 6 查找

查找(search)和插入(insert)这两个普遍的操作不仅本身有直接的应用，还是计算机中许多其他复杂操作和功能的基础。重要性无需赘述。

查找和插入操作的问题描述很简洁：

一个数据元素集合A={a1, a2, … ,an}和一个数据元素x，问x是否在A中。当发现x不在A中的时候，如果需要，则把x放入A中。

这个问题值得研究，是因为提高查找和插入的效率太重要了。在计算机领域优化查找和插入问题的求解方法，有两条维度，不同的数据结构（数据元素集合中数据存储的方式）和优化的查找和插入算法。

本章，书中给出了4个方面的讨论

1. 无序元素列表上的查找和插入（用列表或数组存储，线性查找、尾端插入）

2. 有序元素列表上的查找与插入（用列表或数组存储，对分（折半）查找、有序插入）

3. 搜索二叉树上的查找与插入（搜索二叉树存储）

4. 平衡二叉树上的查找与插入（AVL存储）

【作者感受】

查找和插入是数据结构、算法课程的重点核心内容之一。

如果想从专业的角度学习，还是建议直接看数据结构或算法教材，收获会更大，学习曲线不难。

如果想从科普的角度学习，个人觉得本书的趣味性（当然这本书不是以趣味性这个角度来写书的）或者说吸引度不够，因为作者还是用专业术语在描述，对初学者有学习壁垒。

初学时，建议可以去听听一个好的讲者来讲查找，然后再自己学习，再次强调，学习查找和插入是很能训练计算思维的。我还记得，以前给非计算机专业的学生讲计算机通识课时，只有一节课时间，用的就是查找问题，当然讲的会更加不专业一些，试图有些趣味性，勾起学生的兴趣，能够促进其主动取学习就好了。