数据结构与算法之查找

查找的概述

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. 最坏情况：如果我们要找的元素恰好是线性表的最后一个元素，那么我们需要进行
   标签：index,哈希,tableSize,元素,算法,查找,key,数据结构
   From： https://blog.csdn.net/yuange1666/article/details/144874134