欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-14 20:35:02
...

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

相关标签: 数据结构与算法