顺序表的查找

按位查找

GetElem(L, i) 获取顺序表中第 i 个位置的元素。

由于顺序表连续存储，可通过地址公式或数组下标直接访问：

L.data[i - 1]

时间复杂度：O(1)。

按值查找

LocateElem(L, e) 查找第一个值等于 e 的元素，并返回其位序。

基本思路：从表头开始依次比较，找到则返回 i + 1，遍历结束仍未找到则返回失败标记。

时间复杂度：

  • 最好情况：第一个元素命中，O(1)。
  • 最坏情况：最后一个元素命中或查找失败，O(n)。
  • 平均情况：元素位置等概率时，O(n)。

结构类型比较

C 语言中结构体通常不能直接用 == 比较整体是否相等，应逐个比较关键分量，或定义专门的比较函数。

有序表补充

若顺序表内元素有序，按值查找可使用二分查找，时间复杂度可降为 O(log_2 n)。无序顺序表通常只能顺序查找。

关联

顺序表按位查找优于链表，见 顺序表与链表对比。链表查找见 单链表的查找与建立。