Python常见查找算法

1.关键字定义
查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
查找表（Search Table）：由同一类型的数据元素构成的集合
关键字（Key）：数据元素中某个数据项的值，又称为键值
主键（Primary Key）：可唯一的标识某个数据元素或记录的关键字

2.查找表按照操作方式可分为：
①静态查找表
a)查询某个“特定的”数据元素是否在表中
b)检索某个“特定的”数据元素和各种属性
②动态查找表
a)查找时插入数据
b)查找时删除数据

3.按查找的数据可分为：
①无序查找
也就是数据不排序的线性查找，遍历数据元素
②有序查找
查找表中的数据必须按某个主键进行某种排序！

4.顺序查找/线性查找（无序）
①定义
顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。该算法的时间复杂度为O(n)。
②基本思路
因为时无序的，所以没有任何的计算规则，只能从头到末尾，一个个遍历。
从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。
③优缺点
优点：是对表中数据元素的存储没有要求
缺点：是当n 很大时，平均查找长度较大，效率低
④算法实现

#线性查找/顺序查找
def linear_search(list,key):
    result ={}
    for i in range(len(list)):
        if list[i] == key:
            result["iddex"] = i
            result["value"] = key
    return result

5.二分法查找（有序）
①算法简介：
二分查找（Binary Search），是一种在有序数组中查找某一特定元素的查找算法。查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
这种查找算法每一次比较都使查找范围缩小一半。
②算法描述
给与一个有序的列表
1.取列表索引的最小索引low和最大的索引high，然后算平均值mid
2.把查找的key与list[mid]比较
3.如果key大于list[mid],则key在list[mid]和list[high]之间，low=mid-1，继续切片list，重复1，2步骤
4.如果key小于list[mid],则key在list[low]和list[mid]之间，high=mid+1，继续切片list，重复1，2步骤
5.如果key等于list[mid]，则找到key
③算法实现

#二分查找
def binary_searcH(list,key):
    print(list,key)
    result ={}
    low = 0
    high = len(list)-1
    times = 0
    while low <high:
        times +=1
        mid = int((low+high)/2)
        print(mid,times)
        if key < list[mid]:
            high = mid -1
        elif key > list[mid]:
            low = mid +1
        else:
          result["index"] = list[mid]
          result["value"] = key
          return result
    else:
        print('total times:', times)
        return result

6.插值查找（有序）
①算法简介
插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的 查找方法，其核心就在于插值的计算公式 (key-a[low])/(a[high]-a[low])*(high-low)。
时间复杂度o(logn)但对于表长较大而关键字分布比较均匀的查找表来说，效率较高。
②算法思想
基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
③复杂度分析
时间复杂性：如果元素均匀分布，则O（log log n）），在最坏的情况下可能需要 O（n）。
空间复杂度：O（1）。
④算法实现
基于二分查找
计算mid用公式： mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))
注意：list不要有重复记录，否则有可能死循环

def interpolat_search(list,key):
    result = {}
    low = 0
    high = len(list) - 1
    times = 0
    while low < high:
        times += 1
        mid = low + int((high - low) * (key - list[low]) / (list[high] - list[low]))
        print(mid, times,low,high,key,list[mid])
        if key < list[mid]:
            high = mid - 1
        elif key > list[mid]:
            low = mid + 1
        else:
            result["index"] = list[mid]
            result["value"] = key
            return result
    else:
        print('total times:', times)
        return result

7.斐波那契查找
①算法简介：
斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、····，在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。
②算法描述
斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为Fn，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
③复杂度分析
最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。
④算法实现
注意：需要一个现成的斐波那契列表。其最大元素的值必须超过查找表中元素个数的数值。

#生成斐波那契数列
def generate_fibonacci_list(max=200):
    list = []
    first = 0
    second =1
    index =0
    while index <max:
        list.append(second)
        first,second = second,first+second
        index = index +1

    return list

#斐波那契查找
def fibonacci_search(list,key):
    result = {}
    fib = generate_fibonacci_list(20)
    print(fib)
    low =0
    high = len(list)-1

    k =0
    while high > fib[k] - 1:
        k +=1
    print(k)
    i= high
    while fib[k]-1>i:
        print(high)
        list.append(list[high])
        i+=1
    print(list)

    #算法主逻辑
    times = 0
    while low <= high:
        times +=1
        if k<2:
            mid = low
        else:
            mid = low +fib[k-1]-1
        print("low:{},mid:{},high:{}".format(low,mid,high))
        if key < list[mid]:
            high = mid-1
            k-=1

        elif key > list[mid]:
            low = mid +1
            k-=2

        else:
            if mid <= high:
                result["index"] = mid
                result["value"] = list[mid]
                break
            else:
                result["index"] = high
                result["value"] = list[high]
                break
    print('total times',times)
    return result

8.二叉树查找算法
#平衡查找树之2-3查找树、平衡查找树之红黑树（Red-Black Tree）、B树和B+树（B Tree/B+ Tree）需要花时间来研究
①算法简介
二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
②算法思想
二叉查找树（BinarySearch Tree）或者是一棵空树，或者是具有下列性质的二叉树：
1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3）任意节点的左、右子树也分别为二叉查找树。
③ 复杂度分析
它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡。

# 二叉树查找 Python实现
class BSTNode:
    """
    定义一个二叉树节点类。
    以讨论算法为主，忽略了一些诸如对数据类型进行判断的问题。
    """
    def __init__(self, data, left=None, right=None):
        """
        初始化
        :param data: 节点储存的数据
        :param left: 节点左子树
        :param right: 节点右子树
        """
        self.data = data
        self.left = left
        self.right = right


class BinarySortTree:
    """
    基于BSTNode类的二叉查找树。维护一个根节点的指针。
    """
    def __init__(self):
        self._root = None

    def is_empty(self):
        return self._root is None

    def search(self, key):
        """
        关键码检索
        :param key: 关键码
        :return: 查询节点或None
        """
        bt = self._root
        while bt:
            entry = bt.data
            if key < entry:
                bt = bt.left
            elif key > entry:
                bt = bt.right
            else:
                return entry
        return None

    def insert(self, key):
        """
        插入操作
        :param key:关键码
        :return: 布尔值
        """
        bt = self._root
        if not bt:
            self._root = BSTNode(key)
            return
        while True:
            entry = bt.data
            if key < entry:
                if bt.left is None:
                    bt.left = BSTNode(key)
                    return
                bt = bt.left
            elif key > entry:
                if bt.right is None:
                    bt.right = BSTNode(key)
                    return
                bt = bt.right
            else:
                bt.data = key
                return

    def delete(self, key):
        """
        二叉查找树最复杂的方法
        :param key: 关键码
        :return: 布尔值
        """
        p, q = None, self._root     # 维持p为q的父节点，用于后面的链接操作
        if not q:
            print("空树！")
            return
        while q and q.data != key:
            p = q
            if key < q.data:
                q = q.left
            else:
                q = q.right
            if not q:               # 当树中没有关键码key时，结束退出。
                return
        # 上面已将找到了要删除的节点，用q引用。而p则是q的父节点或者None（q为根节点时）。
        if not q.left:
            if p is None:
                self._root = q.right
            elif q is p.left:
                p.left = q.right
            else:
                p.right = q.right
            return
        # 查找节点q的左子树的最右节点，将q的右子树链接为该节点的右子树
        # 该方法可能会增大树的深度，效率并不算高。可以设计其它的方法。
        r = q.left
        while r.right:
            r = r.right
        r.right = q.right
        if p is None:
            self._root = q.left
        elif p.left is q:
            p.left = q.left
        else:
            p.right = q.left

    def __iter__(self):
        """
        实现二叉树的中序遍历算法,
        展示我们创建的二叉查找树.
        直接使用python内置的列表作为一个栈。
        :return: data
        """
        stack = []
        node = self._root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            yield node.data
            node = node.right
 if __name__ == '__main__':
    list = random_list(100)
    key = 5
    result ={}
    list.sort()
    print(list)
    bs_tree = BinarySortTree()
    for i in range(len(list)):
        bs_tree.insert(list[i])
    bs_tree.insert(1002)
    bs_tree.delete(58)
    for i in bs_tree:
        print(i)

9.分块查找（有序）
①算法简介
要求是顺序表，分块查找又称索引顺序查找，它是顺序查找的一种改进方法。
②算法思想
将n个数据元素”按块有序”划分为m块（m ≤ n）。
每一块中的结点不必有序，但块与块之间必须”按块有序”；
即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；
而第2块中任一元素又都必须小于第3块中的任一元素，……
③算法流程
a)先选取各块中的最大关键字构成一个索引表；
b)查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；
c)在已确定的块中用顺序法进行查找。
④复杂度分析
时间复杂度：O(log(m)+N/m)

10.哈希查找
①算法简介
哈希表就是一种以键-值(key-indexed) 存储数据的结构，只要输入待查找的值即key，即可查找到其对应的值。
②算法思想
哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
③算法流程
a).用给定的哈希函数构造哈希表；
b).根据选择的冲突处理方法解决地址冲突；
　常见的解决冲突的方法：拉链法和线性探测法。
c).在哈希表的基础上执行哈希查找。
④复杂度分析
单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。
⑤代码实现

class HashTable:
    def __init__(self, size):
        self.elem = [None for i in range(size)]  # 使用list数据结构作为哈希表元素保存方法
        self.count = size  # 最大表长
        self.result = {}

    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:  # 说明没找到或者循环到了开始的位置
                break
        self.result["index"] = address
        self.result["value"] = self.elem[address]

   #程序入口 
   if __name__ == '__main__':
    list = random_list(100)
    key = 5
    result ={}
    list.sort()
    hash_table = HashTable(len(list))
    for i in list:
        print(i)
        hash_table.insert_hash(i)
    print('in')
    for i in hash_table.elem:
        if i:
            print((i, hash_table.elem.index(i)))
    print("\n")
    hash_table.search_hash(15)
    result = hash_table.result
    print(result)
    hash_table.search_hash(33)
    result = hash_table.result
    print(result)