小结

• 线性查找是一种最基础的查找方法，通过遍历数据结构 + 判断条件实现查找。
• 二分查找利用数据的有序性，通过循环不断缩小一半搜索区间来实现查找，其要求输入数据是有序的，并且仅适用于数组或基于数组实现的数据结构。
• 哈希查找借助哈希表来实现常数阶时间复杂度的查找操作，体现以空间换时间的算法思想。

Table. 三种查找方法对比

	线性查找	二分查找	哈希查找
适用数据结构	数组、链表	数组	数组、链表
输入数据要求	无	有序	无
平均时间复杂度 查找 / 插入 / 删除	\(O(n)\) / \(O(1)\) / \(O(n)\)	\(O(\log n)\) / \(O(n)\) / \(O(n)\)	\(O(1)\) / \(O(1)\) / \(O(1)\)
最差时间复杂度 查找 / 插入 / 删除	\(O(n)\) / \(O(1)\) / \(O(n)\)	\(O(\log n)\) / \(O(n)\) / \(O(n)\)	\(O(n)\) / \(O(n)\) / \(O(n)\)
空间复杂度	\(O(1)\)	\(O(1)\)	\(O(n)\)