数据结构与算法之查找

查找的概述

1. 查找操作的定义

查找是按照关键字进行的检索。查找表是由同一类型的数据元素构成的集合，关键字是数据元素（或记录）中某个数据项的值，用它可以标识（或识别）一个数据元素。其中，主关键字可以唯一标识一个数据元素，而次关键字则不能。

2. 查找表的四种操作

1. 查询某个特定的数据元素是否在表中；
2. 查询某个特定元素的各个属性；
3. 在查找表中插入一个数据元素；
4. 从查找表中删除一个数据元素。

3.查找概述

├── 查找定义

│ ├── 查找表：数据元素集合

│ └── 关键字：标识数据元素的值

│ ├── 主关键字：唯一标识

│ └── 次关键字：辅助标识

└── 查找表操作

├── 查询元素存在性

├── 查询元素属性

├── 插入数据元素

└── 删除数据元素

基于线性表的查找

1. 顺序查找

顺序查找适用于任何线性表（无序/有序/顺序表/链表均可）。基本思想是从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功；若整个表检测完仍未找到与给定值相等的关键码，则查找失败。

k = 35
for i in range(len(list)):
    if list[i] == k:
        print(i)
        break
    else:
        print(False)

2. 顺序查找的时间复杂度分析

• 最大查找长度：n
• 平均查找长度：(n+1)/2

平均查找长度怎么来的？

1. 最佳情况：如果我们要找的元素恰好是线性表的第一个元素，那么我们只需要进行一次比较，即查找长度为 1。
2. 最坏情况：如果我们要找的元素恰好是线性表的最后一个元素，那么我们需要进行𝑛次比较，即查找长度为 𝑛。
3. 一般情况：如果我们要找的元素是线性表中的第𝑖个元素，那么我们需要进行𝑖次比较。

为了找到平均查找长度，我们需要计算所有可能查找长度的平均值。这可以通过求和所有可能的查找长度，然后除以可能的查找长度的数量来实现。由于每个元素被查找的概率是相同的，我们有：

这个求和是一个等差数列的求和，其和为：

因此，平均查找长度为：

3. 顺序查找的优缺点

• 优点：简单，容易编写
• 缺点：效率低下

4. 折半查找

折半查找的前提是元素有序存放。其思想是类似翻书，通过比较中间位置的元素与待查找值来缩小查找区间。折半查找通常也被称为二分查找，是一种在有序数组中查找特定元素的高效算法。它通过比较数组中间元素与目标值来决定是继续在左半部分还是右半部分查找，从而将搜索范围缩小一半（将时间复杂度优化到对数级别）。

伪代码

li = [...]              # 假设这是一个已经排序的列表
k = int                  # 要查找的元素
l = 0                    # 左指针
r = len(li) - 1         # 右指针
mid = (l + r) // 2      # 计算中间索引
while l <= r:
    if li[mid] < k:
        l = mid + 1
    else:
        r = mid - 1
    mid = (l + r) // 2  # 重新计算中间索引

装嵌在函数里

l = 0
r = len(li) - 1

def check(li, k):   
    while l <= r:
        mid = (l + r) // 2
        if li[mid] == k:
            return mid  # 返回找到元素的索引
        elif li[mid] < k:
            l = mid + 1
        else:
            r = mid - 1
    return -1  # 表示未找到

5.性能分析

1. 基于线性表的查找小结

├── 顺序查找

│ ├── 定义：逐个比较

│ ├── 时间复杂度

│ │ ├── 最大长度：n

│ │ └── 平均长度：(n+1)/2

│ └── 优缺点

│ ├── 优点：简单易编写

│ └── 缺点：效率低下

└── 折半查找(二分查找)

├── 前提：元素有序

├── 思想：类似翻书

└── 查找过程

├── 比较中间元素

├── 缩小查找区间

└── 查找成功或失败

基于树的查找

1. 二叉排序树的定义

二叉排序树是一种特殊的二叉树，它满足以下性质：

• 如果左子树非空，左子树所有结点的值都小于根结点的值，且左子树也是一棵二叉排序树。
• 如果右子树非空，右子树所有结点的值都大于或等于根结点的值，且右子树也是一棵二叉排序树。

2. 二叉排序树的查找过程

查找过程类似于折半查找：

1. 从根结点开始，将给定值与当前结点的值进行比较。
2. 如果相等，则查找成功。
3. 如果给定值小于当前结点的值，则在左子树中继续查找。
4. 如果给定值大于当前结点的值，则在右子树中继续查找。
5. 如果当前结点为空，则查找失败。

3. 二叉排序树的查找效率

• 最好情况：树完全平衡，查找长度约等于O(logn)。
• 最坏情况：树退化成一条直线，查找长度为O(n)。

4. 二叉排序树的构造过程

从第一个元素开始，依次插入元素到二叉排序树中。每个新插入的元素都会根据其值与已有结点的比较结果被放置在正确的位置。

思维导图发展思考

基于树的查找

├── 二叉排序树定义

│ ├── 左子树值 < 根结点值

│ └── 右子树值 ≥ 根结点值

├── 查找过程

│ ├── 比较给定值与当前结点值

│ ├── 根据比较结果决定搜索方向

│ └── 重复直到找到或结点为空

├── 查找效率

│ ├── 最好情况：O(log n)

│ └── 最坏情况：O(n)

└── 构造过程

└── 依次插入元素，根据值比较放置

5. 二叉排序树的平衡问题

二叉排序树在最坏情况下会退化成一条直线，这通常是因为插入的元素顺序导致的。为了解决这个问题，可以采用平衡二叉树（如AVL树或红黑树）来保证树的平衡。

6. 二叉排序树的查找算法（伪代码）

BiTreeSearch(root, e)
    if root is null
        return 查找失败
    if e == root.data
        return 查找成功
    if e < root.data
        return BiTreeSearch(root.left, e)
    if e > root.data
        return BiTreeSearch(root.right, e)

哈希

1. 哈希查找的基本概念

哈希查找是一种通过使用哈希函数将输入（例如关键字）转换为索引值，从而在常数时间内访问到数据的查找方法。这种方法不依赖于数据的顺序，而是通过计算得到数据的存储位置。（通过哈希编码对值进行映射，即获得对应关系）

2. 哈希函数

哈希函数是哈希查找的核心，它将输入值（关键字）映射到一个固定范围内的整数，这个整数通常用作数组的索引。一个好的哈希函数应满足以下条件：

• 计算简单：快速计算就能得到哈希
• 分布均匀：关键字的哈希值应尽可能均匀分布在哈希表中，以减少冲突

3. 冲突解决

冲突是指两个不同的关键字通过哈希函数计算得到相同的哈希值。解决冲突的常用方法包括：

• 开放寻址法：当发生冲突时，按照某种策略（如线性探测、二次探测或双重哈希）寻找空的哈希表位置。
• 链表法：每个哈希表位置存储一个链表，所有映射到该位置的元素都存储在这个链表中。

4. 哈希表的动态扩容

随着元素的增加，哈希表可能会变得拥挤，导致更多的冲突。动态扩容是解决这个问题的一种方法，即在哈希表过载时增加其大小，并重新哈希所有元素。

5. 哈希查找的性能

• 平均性能：在理想情况下，哈希查找的平均时间复杂度为 O(1)O(1)。
• 最坏性能：如果所有元素都映射到同一个哈希表位置，那么最坏时间复杂度为 O(n)，其中 n 是元素的数量。

哈希查找

├── 基本概念

│ └── 通过哈希函数快速访问数据

├── 哈希函数

│ ├── 计算简单

│ └── 分布均匀

├── 冲突解决

│ ├── 开放寻址法

│ └── 链表法

├── 动态扩容

│ └── 增加哈希表大小，重新哈希元素

└── 性能

├── 平均性能：O(1)

└── 最坏性能：O(n)

6. 哈希函数的设计原则

• 简单性：哈希函数的计算应该简单，以减少计算时间。
• 均匀性：哈希函数应该能够将关键字均匀地分布在哈希表中，减少冲突。
• 确定性：对于同一个关键字，无论何时计算，哈希函数都应该返回相同的哈希值。

7. 常用的哈希函数类型

• 直接定址法：如 H(key)=key−1949，适用于关键码集合连续且较小的情况。
• 除留余数法：如 H(key)=key%p，其中 p 是一个不大于哈希表表长 m 的素数。
• 平方取中法：对关键码平方后，取中间的若干位作为哈希地址。

8.伪代码

1. 哈希函数示例（除留余数法）

plaintext

function hash(key, tableSize):

return key % tableSize

2. 初始化哈希表

plaintext

function initializeHashTable(size):

create an array of size 'size' with all elements set to NULL or a special value indicating empty slot

3. 哈希查找（开放寻址法 - 线性探测）

plaintext

function hashSearch(key, hashTable, tableSize):

index = hash(key, tableSize)

while hashTable[index] is not NULL and hashTable[index] is not key:

index = (index + 1) % tableSize

return index

4. 插入元素（开放寻址法 - 线性探测）

plaintext

function hashInsert(key, value, hashTable, tableSize):

index = hash(key, tableSize)

while hashTable[index] is not NULL:

index = (index + 1) % tableSize

hashTable[index] = (key, value)

5. 删除元素（开放寻址法 - 线性探测）

plaintext

function hashDelete(key, hashTable, tableSize):

index = hash(key, tableSize)

while hashTable[index] is not NULL:

if hashTable[index].key == key:

hashTable[index] = NULL

return true

index = (index + 1) % tableSize

return false

6. 哈希查找（链表法）

plaintext

function hashSearch(key, hashTable, tableSize):

index = hash(key, tableSize)

for each element in hashTable[index]:

if element.key == key:

return element.value

return NULL

7. 插入元素（链表法）

plaintext

function hashInsert(key, value, hashTable, tableSize):

index = hash(key, tableSize)

if hashTable[index] is NULL:

create a new linked list at index

else:

append a new node with (key, value) to the linked list at index

8. 删除元素（链表法）

plaintext

function hashDelete(key, hashTable, tableSize):

index = hash(key, tableSize)

current = hashTable[index].head

prev = NULL

while current is not NULL:

if current.key == key:

if prev is NULL:

hashTable[index].head = current.next

else:

prev.next = current.next

return true

break

prev = current

current = current.next

return false