Python线性查找与二分查找，如何快速定位目标元素？

本文共计4728个文字，预计阅读时间需要19分钟。

查找算法是用来检索序列（群体）数据中是否存在特定数据（关键字）的方法。常用查找算法包括：

+ 线性查找：逐个比较序列中的元素，直到找到目标或遍历完整个序列。+ 二分查找：也称为有序查找，适用于有序序列，通过不断缩小查找范围来提高效率。

查找算法是用来检索序列数据（群体）中是否存在给定的数据（关键字），常用查找算法有：

• 线性查找： 线性查找也称为顺序查找，用于在无序数列中查找。
• 二分查找： 二分查找也称为折半查找，其算法用于有序数列。
• 插值查找： 插值查找是对二分查找算法的改进。
• 分块查找： 又称为索引顺序查找，它是线性查找的改进版本。
• 树表查找： 树表查找又可分二叉查找树、平衡二叉树查找。
• 哈希查找： 哈希查找可以直接通过关键字查找到所需要数据。

因树表查找、哈希查找的所需篇幅较多，就不在本文讲解。本文将详细介绍除树表、哈希之外的查找算法，并分析每一种算法的优点和缺点，并提出相应的优化方案。

1. 线性查找

线性查找也称为顺序查找，线性查找属于原始、穷举、暴力查找算法。容易理解、编码实现也简单。但是在数据量较多时，因其算法思想是朴素、穷举的，算法中没有太多优化设计，性能会很低下。

线性查找思想：

• 从头至尾逐一扫描原始列表中的每一个数据，并和给定的关键字进行比较。
• 如果比较相等，则查找成功。
• 当扫描结束后，仍然没有找到与给定关键字相等的数据，则宣布查找失败。