二分查找

原理：以升序数列为例，比较一个元素与数列中的中间位置的元素的大小，如果比中间位置的元素大，则继续在后半部分的数列中进行二分查找；如果比中间位置的元素小，则在数列的前半部分进行比较；如果相等，则找到了元素的位置。每次比较的数列长度都会是之前数列的一半，直到找到相等元素的位置或者最终没有找到要找的元素。

代码

def BinSearch(array, target, start, end):
    while True:
        pos = (start + end) // 2
        if start == end - 1:
            break
        if array[pos] == target:
            return pos
        elif array[pos] <= target:
            start = pos
        else:
            end = pos
    return None


def main():
    array = [1, 2, 3, 4, 5, 67, 88, 97, 887, 998, 999]
    print(BinSearch(array, 999, 0, len(array)))


if __name__ == '__main__':
    main()

分块查找算法

原理：分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。分块查找的基本思想是：首先查找索引表，索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。然后在已确定的块中进行顺序查找，由于块内无序，只能用顺序查找。
算法思想

1. 将n个数据元素"按块有序"划分为m块（m ≤ n）。
2. 每一块中的结点不必有序，但块与块之间必须"按块有序"；
3. 即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；
4. 而第2块中任一元素又都必须小于第3块中的任一元素
5. 选取各块中的最大关键字构成一个索引表；
6. 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；
7. 在已确定的块中用顺序法进行查找。

代码

def BlockSearch(array, target, num_of_block):
    new_array = [array[i:i + num_of_block] for i in range(0, len(array), num_of_block)]
    block_info = []
    for i in range(len(new_array)):
        block_info.append((max(new_array[i]), i * num_of_block))
    index = 0
    for i in range(len(block_info)):
        if target <= block_info[i][0]:
            index = block_info[i][1]
            break
    for i in range(index, index + num_of_block):
        if array[i] == target:
            return i
    else:
        return None


def main():
    nums_of_block = 4
    array = [1, 2, 3, 4, 5, 67, 88, 97, 887, 998, 999]
    print(BlockSearch(array, target=887, num_of_block=nums_of_block))


if __name__ == '__main__':
    main()

插值查找算法

原理：插值查找（Insert Value Search）是二分查找的一种改良，主要是改良了mid的值，mid的值由原来的mid = (left + right) / 2而变成了自适应获取mid的值mid = left + int(key - arr [left]) / (arr [right] - arr [left]) * (right - left)。对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快。而关键字分布不均匀的情况下，该方法不一定比二分查找要好。

代码

def InterpolationSearch(array, target, start, end):
    while True:
        pos = start + int((end - start) * (target - array[start]) / (array[end] - array[start]))
        if start >= end:
            break
        if array[pos] == target:
            return pos
        elif array[pos] <= target:
            start = pos + 1
        else:
            end = pos - 1
    return None


def main():
    array = [1, 2, 3, 4, 5, 67, 88, 97, 887, 998, 999]
    print(InterpolationSearch(array, 89, 0, len(array) - 1))


if __name__ == '__main__':
    main()

hash查找算法

原理

1. 哈希函数：也称散列函数，是Hash表的映射函数，它可以把查找表中的关键字映射成该关键字对应的地址函数，表示如下：Hash(key)=Addr,（地址可以是数组下标、索引、内存地址等）
2. 哈希函数能使对一个数据序列的访问过程变得更加迅速有效，通过哈希函数数据元素能够被很快的进行定位。
3. 哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。

4. 索引值的确定

   • 直接定址法：直接取关键字的某个线性函数值作为散列地址，例如：H(key)=a×key+b,(a和b均为常数)，适合关键字分布基本连续的情况，否则容易造成存储空间浪费。
   • 除留余数法：(最常用) 假定表长为m，取一个不大于m但最接近或者等于m的质数P，例如：H(key)=key%P
   • 数字分析法：比如有一组value1=112233，value2=112633，value3=119033，针对这样的数我们分析数中间两个数比较波动，其他数不变。那么我们取key的值就可以是key1=22,key2=26,key3=90。适合于已知关键字的集合分布，关键字位数较大的情况。
   • 平方取中法：取关键字的平法值的中间几位作为散列地址。适合于不是道关键字分布，且关键字每一位取值不均匀或均小于散列地址所需的位数。
   • 折叠法：举个例子，比如value=135790，要求key是2位数的散列值。那么我们将value变为13+57+90=1601，然后去掉高位“1”,此时key=60，这就是他们的哈希关系。这样做的目的就是key与每一位value都相关，来达到“散列地址”尽可能分散的目的。适合于不需要知道关键字分布，关键字位数较多的情况。

5. 冲突：两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。

   • 开放定址法：这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=（H（key）+di）% m i=1，2，…，n其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

     • 线性探测再散列：这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
     • 二次探测再散列：这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
     • 伪随机探测再散列，di=伪随机数序列。具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。
   • 再哈希法：同时构造多个不同的哈希函数：当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
   • 链地址法：这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
   • 建立公共溢出区：这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

代码

import numpy as np
import string
import random

class HashSearch:
    def __init__(self):
        self.array_len = 1000
        self.conflict_len = 100
        self.array = np.array([np.nan for i in range(self.array_len)])
        # 建立公共溢出区
        self.conflict = np.array([np.nan for i in range(self.conflict_len)])
        # 统计溢出数
        self.conflict_times = 0
        self.digit = int(len(str(self.array_len))) - 1

    def add(self, value):
        try:
            hash_id = int(str(hash(value))[-self.digit:])
            if np.isnan(self.array[hash_id]):
                self.array[hash_id] = value
            else:
                self.handle_conflict(value)
        except TypeError as e:
            print(e)
            # print("unhashable type")

    def handle_conflict(self, value):
        self.conflict_times += 1
        for i in range(len(self.conflict)):
            if np.isnan(self.conflict[i]):
                self.conflict[i] = value
                break
        if self.conflict_times >= self.conflict_len // 3:
            self.increase()

    def search(self, value):
        hash_id = int(str(hash(value))[-self.digit:])
        if self.array[hash_id] == value:
            return hash_id, value
        else:
            for i in range(self.conflict_len):
                if self.conflict[i] == value:
                    return i + self.array_len, value

    def increase(self):
        self.array_len *= 10
        self.conflict_len *= 10
        self.array = np.append(self.array, self.conflict)
        new_array = np.array([np.nan for i in range(self.array_len)])
        self.conflict = np.array([np.nan for i in range(self.conflict_len)])
        for i in range(len(self.array)):
            pos = int(str(hash(self.array[i]))[-self.digit:])
            if not np.isnan(new_array[pos]):
                new_array[pos] = self.array[i]
            else:
                self.handle_conflict(self.array[i])
        self.array = new_array


h = HashSearch()
for i in range(100):
    data = int(''.join(random.sample("0123456789", 5)))
    h.add(data)
h.add(12345)
for i in range(100):
    data = int(''.join(random.sample("0123456789", 5)))
    h.add(data)
print(hash(12345))
print(h.search(12345))

二叉树查找

原理

二叉查找树(Binary Search Tree)，它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。那么，这棵树就是二叉查找树。如下图所示：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
   2.任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
2. 任意节点的左、右子树也分别为二叉查找树。
3. 没有键值相等的节点（no duplicate nodes）。

代码

# 定义节点
class Node:
    def __init__(self, value=None, father=None, left_child=None, right_child=None):
        self.father = father
        self.left_child = left_child
        self.right_child = right_child
        self.value = value

    def __repr__(self):
        return "".join(["Node Value:", str(self.value), "\tid:", str(id(self))])


# 定义树**
class BinarySortTree:
    def __init__(self):
        self.root = Node()

    # 向树中添加节点**

    def add(self, value):
        if isinstance(value, int) or isinstance(value, float):
            value = [value]
        if not isinstance(value, list):
            raise Exception('Type Error: Type must be int float or list')
        val = value
        if self.root.value is None:
            self.root.value = val.pop(0)
        for value in val:
            cur = self.root
            while True:
                if value < cur.value:
                    if cur.left_child is None:
                        cur.left_child = Node(value, father=cur)
                        break
                    else:
                        cur = cur.left_child
                elif value > cur.value:
                    if cur.right_child is None:
                        cur.right_child = Node(value, father=cur)
                        break
                    else:
                        cur = cur.right_child
                elif value == cur.value:
                    break


    # 查找节点

    def find(self, value):
        node = self.root
        while True:
            if not node.left_child and not node.right_child and value != node.value:
                return None
            elif value < node.value:
                if node.left_child:
                    node = node.left_child
                else:
                    return None
            elif value > node.value:
                if node.right_child:
                    node = node.right_child
                else:
                    return None
            else:
                return node


    # 查找树中最大最小值
    @staticmethod
    def tree_find_max(node):
        """
        找节点树的最大值
        :param node: 节点
        :return: node
        """
        while True:
            if node.right_child:
                node = node.right_child
            else:
                return node

    @staticmethod
    def tree_find_min(node):
        """
        找节点树的最小值
        :param node: 节点
        :return: node
        """
        while True:
            if node.left_child:
                node = node.left_child
            else:
                return node

    #三种树的遍历方式

    # 中序遍历
    def __inorderTraversal(self, node):
        if node is None:
            return
        self.__inorderTraversal(node.left_child)
        print(node.value, end=' ')
        self.__inorderTraversal(node.right_child)

    # 先序遍历
    def __preorderTraversal(self, node):
        if node is None:
            return
        print(node.value, end=' ')
        self.__preorderTraversal(node.left_child)
        self.__preorderTraversal(node.right_child)

    # 后序遍历
    def __postorderTraversal(self, node):
        if node is None:
            return
        self.__postorderTraversal(node.left_child)
        self.__postorderTraversal(node.right_child)
        print(node.value, end=' ')

    def print(self, order='inorder'):
        if order == 'inorder':
            self.__inorderTraversal(self.root)
        elif order == 'preorder':
            self.__preorderTraversal(self.root)
        elif order == 'postorder':
            self.__postorderTraversal(self.root)