1 Introduction

1.1 Intro

线性搜索或顺序搜索是一种寻找某一特定值的搜索算法,指按一定的顺序检查数组中每一个元素,直到找到所要寻找的特定值为止。是最简单的一种搜索算法.

线性搜索在物理上可以顺序, 也可以连接, 但是逻辑上是顺序存储的.

相比哈希检索, 线性检索的数据没有任何限定, 没有额外的键值空间消耗, 没有唯一值的
限定.

1.2 Classify

  • 无序表查找: 数据本身没有经过排序, 通过暴力遍历查找数据
  • 有序表查找: 二分查找, 差值查找, 斐波那契查找, 线性索引查找

2.1 Analysis

检索过程: 针对线性表里的所有记录,逐个进行关键码和给定值的比较

  • 若某个记录的关键码和给定值比较相等,则检索成功
  • 否则检索失败

物理存储: 在物理上可以顺序, 也可以链表存储, 但在逻辑上是顺序存储的

2.2 性能分析

使用暴力搜索, 时间复杂度: O(n)

2.3 Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def sequential_search(lis, key):
for i in range(len(lis)):
if lis[i] == key:
return i
return None


if __name__ == '__main__':
src = [1, 0, 123, 53, 293, 8, 123, 22, 54, 7, 92, 303, 222]
index = sequential_search(src, 123)
if index:
print('下标:', index, ' 值:', src[index])
else:
print('未找到')

3.1 Analysis

数据本身在存储或者取出时, 必须先经过排序, 以便在后续的搜索过程中能够更加方便快捷.
一般而言, 在搜索算法中, 都要求数据为静态数据, 不会经常性的进行数据的更新和删除操作.

对于大数据, 如果使用暴力搜索, 性能可能不如想象, 在对已排序数据进行查找时, 则有多种
方式:

  • 二分查找: 查找表中不断比较中间元素与查找值,以二分之一的倍率进行表范围的缩小
  • 插值查找: 对半过滤还不够狠, 如果以10分之9的倍率进行范围缩小, 能够更快的进行缩减, 使用value = (key - list[low])/(list[high] - list[low])公式来完成
  • 斐波那契查找: 利用斐波那契数据列表降低搜索范围

3.2 性能分析

时间复杂度: O(logn)

3.3 Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def binary_search(lis, key):
low = 0
high = len(lis) - 1
time = 0

while low < high:
time += 1
# 插值查找算法: low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))
mid = int((low + high) / 2)
if key < lis[mid]:
high = mid - 1
elif key > lis[mid]:
low = mid + 1
else:
# 打印折半的次数
print("对半查找的times: %s" % time)
return mid

return None


if __name__ == '__main__':
src = [1, 5, 7, 8, 12, 16, 20, 22, 54, 99, 100, 123, 200, 222, 444]
result = binary_search(src, 99)
if result:
print('下标:', result, ' 查找值:', src[result])
else:
print('查找失败')

4.1 Analysis

顺序索引查找, 这是顺序和二分法的折衷, 既有较快的检索, 又能保证灵活的更改.

基本思路: 按照块有序来进行数据排序, 其中块中的关键码并非有序的, 其中索引表记录了各个块中的最大关键码以及各个块的起始位置, 相当于C 中的指针概念.

索引表: 一个递增有序的表结构

block-search

4.2 性能分析

时间复杂度: ASL(n) = ASL(b) + ASL(w)

索引表是顺序表: ASL = n^(-2)

索引表是二分: ASL = log2(1 + n/s) + s/2