从查找表的一端开始，依次将每个记录的关键字与给定值进行比较

1. 顺序查找

   • 基本思想：从查找表的一端开始，依次将每个记录的关键字与给定值进行比较。若匹配成功，则查找成功；若遍历整个表仍未找到，则查找失败。
   • 适用场景：适用于顺序存储结构（如数组）和链式存储结构（如单链表），对数据是否有序无要求。
   • 平均查找长度（ASL）：
     • 在等概率情况下，成功查找的平均查找长度为：
       ASL成功=n+12 ASL_{\text{成功}} = \frac{n+1}{2}ASL成功​=2n+1​
       即平均需要比较约一半的元素。
     • 查找失败时，必须比较全部nnn个元素（若设置监视哨，则为n+1n+1n+1次）。
   • 特点：算法简单、实现容易、适应性强（无需排序），但当表长nnn较大时，效率较低，时间复杂度为O(n)O(n)O(n)。

2. 折半查找（二分查找）

   • 前提条件：查找表必须是按关键字有序排列，且采用顺序存储结构（便于通过下标访问中间元素）。
   • 基本逻辑：
     每次将待查关键字与当前查找区间的中间位置元素的关键字比较：
     • 若相等，则查找成功；
     • 若待查值更大，则在右半区间继续查找；
     • 若待查值更小，则在左半区间继续查找。
       重复此过程，直到找到目标或查找区间为空。
   • 特点：效率高，时间复杂度为O(log⁡n)O(\log n)O(logn)，但限制较多（需有序、顺序存储）。后续可通过判定树分析其成功与失败情况下的平均查找长度（ASL）。

# 折半查找示例代码（非递归）defbinary_search(arr,target):left,right=0,len(arr)-1whileleft<=right:mid=(left+right)//2ifarr[mid]==target:returnmid# 返回索引elifarr[mid]<target:left=mid+1else:right=mid-1return-1# 查找失败

在等概率情况下，顺序查找的平均查找长度（ASL，Average Search Length）可以通过数学期望的方法进行推导。

推导过程：

假设查找表中有nnn个元素，且每个元素被查找的概率相等（即等概率），均为：
Pi=1n(i=1,2,…,n) P_i = \frac{1}{n} \quad (i = 1, 2, \dots, n)Pi​=n1​(i=1,2,…,n)

• 查找第1个元素需要比较1次；
• 查找第2个元素需要比较2次；
• …
• 查找第iii个元素需要比较iii次；
• 查找第nnn个元素需要比较nnn次。

由于是“成功查找”的平均情况，我们只考虑目标元素存在于表中的情形。

则平均查找长度为所有查找位置的比较次数的加权平均（权重为概率）：

ASL成功=∑i=1nPi×i=1n∑i=1ni=1n⋅n(n+1)2=n+12 ASL_{\text{成功}} = \sum_{i=1}^{n} P_i \times i = \frac{1}{n} \sum_{i=1}^{n} i = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2}ASL成功​=i=1∑n​Pi​×i=n1​i=1∑n​i=n1​⋅2n(n+1)​=2n+1​

✅ 最终结果：

ASL成功=n+12 \boxed{ASL_{\text{成功}} = \frac{n+1}{2}}ASL成功​=2n+1​​

这说明，在等概率条件下，平均需要比较约一半的元素才能找到目标。

补充说明：

• 若查找失败，则必须遍历整个表（共nnn次比较），所以失败时的 ASL 为nnn。
• 若设置了“监视哨”（sentinel），将待查值放在表尾，则最多比较n+1n+1n+1次即可确定结果。

示例验证：

设n=5n = 5n=5，则：
ASL=1+2+3+4+55=155=3=5+12 ASL = \frac{1+2+3+4+5}{5} = \frac{15}{5} = 3 = \frac{5+1}{2}ASL=51+2+3+4+5​=515​=3=25+1​
符合公式。