数据结构:查找子系统

查找子系统是数据结构中的一个重要部分，它是指在一个数据集合中查找某个特定元素的过程。常见的查找算法有顺序查找、二分查找、分块查找、哈希查找等。下面是这些算法的简单介绍和示例：

1. 顺序查找：将待查找值与查找表中的数据依次进行比较，直到找到为止。

def sequential_search(lst, key):
    for i in range(len(lst)):
        if lst[i] == key:
            return i
    return -1

2. 二分查找：对于有序表，每次将待查找区间缩小一半，直到找到为止。

def binary_search(lst, key):
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] < key:
            low = mid + 1
        elif lst[mid] > key:
            high = mid - 1
        else:
            return mid
    return -1

3. 分块查找：将查找表分成几块，块与块之间是有序的，形成一张索引顺序表，在索引顺序表中查找待查找值，用折半查找的方法确定待查找值在哪一块，然后在确定的块中用顺序查找的方法进行查找。

def block_search(lst, key, block_size):
    blocks = [lst[i:i+block_size] for i in range(0, len(lst), block_size)]
    index = [block[0] for block in blocks]
    block_id = binary_search(index, key)
    if block_id == -1:
        return -1
    else:
        block = blocks[block_id]
        for i in range(len(block)):
            if block[i] == key:
                return block_id * block_size + i
        return -1

4. 哈希查找：基于哈希函数的查找方法，将待查找值通过哈希函数映射到一个桶中，然后在桶中进行查找。

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]
        
    def hash(self, key):
        return key % self.size
    
    def insert(self, key, value):
        h = self.hash(key)
        self.table[h].append((key, value))
        
    def search(self, key):
        h = self.hash(key)
        for k, v in self.table[h]:
            if k == key:
                return v
        return None