Python常见的查找算法（顺序查找、二分查找和哈希查找）

目录

• 1. 顺序查找
• 2. 二分查找
• 3.哈希查找

1. 顺序查找

顺序查找也叫线性查找，顺序查找是所有查找方法中最基础也最简单的一种，一般用于对线性表的查找。它是按照数据在查找表中原有的顺序进行遍历查询的算法。由于需要遍历整个查找表，所以顺序查找的时间复杂度为 O(n)。其实现如下：

def seq_search(li,val):
    for ind,v in enumerate(li):
        if v == val:
            return ind # 如果查找的数在列表里，返回这个数在列表里的索引值
    else:
        return None
li = [8,5,7,9,6,2,4]
print(seq_search(li,9)) # 3

缺点：是当n 很大时，平均查找长度较大，效率低。
优点：是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。

2. 二分查找

二分查找又称折半查找，是常见的搜索算法之一，适用于有序的序列，通过将序列不断的对折分为区间，从而确定查找值是否存在，优点是速度快。

首先，假设列表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

1. 普通实现

def bin_search(li,val):
    left = 0
    right = len(li) - 1
    while left <= right:
        mid = (left + right)//2
        if li[mid] == val:
            return True,mid
        elif li[mid] > val:
            right = mid - 1
        else:
            left = mid +1
    
    return False

li = [1,3,5,8,9,12]
print(bin_search(li,3)) # (True, 1)

2.递归实现

def bin_search(li,val):
    n = len(li)
    if n > 0:
        mid = n//2
        if li[mid] == val:
            return True,mid
        elif li[mid] > val:
            return bin_search(li[:mid-1],val)
        else:
            return bin_search(li[mid+1:],val)

    else:
        return False

li = [1,3,5,8,9,12]
print(bin_search(li,3)) # (True, 1)

优点：比较次数少，查找速度快，平均性能好。
缺点：要求待查表为有序表，且插入删除困难。

3.哈希查找

class HashTable:
'''python实现哈希数据结构及其哈希查找算法：'''
    def __init__(self, size):
        self.elem = [None for i in range(size)]  # 使用list数据结构作为哈希表元素保存方法
        self.count = size  # 最大表长

    def hash(self, key):
        return key % self.count  # 散列函数采用除留余数法

    def insert_hash(self, key):
        """插入关键字到哈希表内"""
        address = self.hash(key)  # 求散列地址
        while self.elem[address]:  # 当前位置已经有数据了，发生冲突。
            address = (address + 1) % self.count  # 线性探测下一地址是否可用
        self.elem[address] = key  # 没有冲突则直接保存。

    def search_hash(self, key):
        """查找关键字，返回布尔值"""
        star = address = self.hash(key)
        while self.elem[address] != key:
            address = (address + 1) % self.count
            if not self.elem[address] or address == star:  # 说明没找到或者循环到了开始的位置
                return False
        return True

Python 哈希表的实现
代码摘自：python哈希实现

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

    def put(self, key, value):
        hashvalue = self.hashfunction(key, len(self.slots))
        if self.slots[hashvalue] is None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = value
        else:
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = value

            else:
                nextslot = self.rehash(hashvalue, len(self.slots))
                while self.slots[nextslot] is not None and self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot, len(self.slots))

                if self.slots[nextslot] is None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = value
                else:
                    self.data[nextslot] = value

    def rehash(self, oldhash, size):
        return (oldhash + 1) % size

    def hashfunction(self, key, size):
        return key % size

    def get(self, key):
        startslot = self.hashfunction(key, len(self.slots))
        data = None
        found = False
        stop = False
        pos = startslot
        while pos is not None and not found and not stop:
            if self.slots[pos] == key:
                found = True
                data = self.data[pos]
            else:
                pos = self.rehash(pos, len(self.slots))
                # 回到了原点，表示找遍了没有找到
                if pos == startslot:
                    stop = True
        return data

    # 重载载 __getitem__ 和 __setitem__ 方法以允许使用 [] 访问
    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, value):
        return self.put(key, value)


if __name__ == '__main__':
    H = HashTable()
    H[54] = "cat"
    H[26] = "dog"
    H[93] = "lion"
    H[17] = "tiger"
    H[77] = "bird"
    H[31] = "cow"
    H[44] = "goat"
    H[55] = "pig"
    H[20] = "chicken"

    print(H.slots)  # [77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]
    print(H.data)  # ['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']
    print(H[20])  # 'chicken'
    H[20] = 'duck'
    print(H[20])  # duck
    print(H[99])  # None