查找

查找一般要掌握顺序查找、二分查找、哈希表查找和二叉排序树查找。要能够快速准确地写出二分查找的代码。

1. 顺序查找

顺序查找就是按照顺序表，一个一个问哎是不是你是不是你，不是就继续问下一个直到找到为止，简单有效的方法。

代码

tips：代码实现中有一个性能优化的点：设置一个哨兵(设置为数组首元素a(0)或者末元素a(n-1)，将哨兵的值设置为待查找关键字key的值)，一般首元素a(0)用得比较多，然后查找时从末元素向前找，若找到就返回相应下标；若找不到，则返回首元素的下标0，表示查找失败。

# sequentialSearch.py

def sequentialSearch(inputArray, lengthOfArray, searchedKey):
    inputArray[0] = searchedKey  # 将查找表(即inputArray)的首元素设置为“哨兵”，并将待查找关键字key的值赋值给“哨兵”
    index = lengthOfArray - 1  # 从查找表的末元素开始向前查找
    while (inputArray[index] != searchedKey):
        index -= 1
    return index # 若查找到符合的位置，则返回相应位置的下标；若返回0，表示查找失败

if __name__ == "__main__":
    inputArray = [0, 3, 9, 6, 45, 32, 68]
    lengthOfArray = len(inputArray)
    print("lengthOfArray is :", lengthOfArray)
    searchedIndex = sequentialSearch(inputArray, lengthOfArray, 45)
    print("index of key = 45 is :", searchedIndex)

运行结果

这里下标从1开始，主要是存储数据从1开始，下标为0的位置作它用（这里作为哨兵），依据数据结构而定。

最好时间复杂度为O(1) --在第一个位置就找到；
最坏时间复杂度为O(n) --在最后一个位置才找到；
平均时间复杂度为O(n)。

2. 有序表查找

一个线性表有序时，对于查找总是很有帮助的。

2.1 二分查找

写在前面：若要求在排序的数组（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数，可尝试用二分查找算法。

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。

注意：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。顺序存储的原因是：查找过程会对下标进行操作，而链式存储只能通过p->next的形式寻找后面的元素，无法对下标进行操作。

查找过程

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

算法时间复杂度

O(log2^n) #是以2为底，n的对数
对于二分查找的时间复杂度，可以将其映射为二叉树。最多查找次数不超过二叉树的深度即log(2 ^ n)+1（对于n个结点的完全二叉树，其深度为log(2^n)+1）。

代码

# binarySearch0823 非递归实现

def binarySearch(inputArray, lenOfArray, key):
    # low high mid
    low = 1
    high = lenOfArray
    while low <= high :
        mid = low + (high - low) // 2
        if inputArray[mid] > key:
            high = mid - 1
        elif inputArray[mid] < key:
            low = mid + 1
        else:
            return mid
    return 0

if __name__ == "__main__":
    inputArray = [0, 1, 2, 3, 5, 12, 12, 12, 15, 29, 55] #其中，下标为0的位置不参与查找
    lenOfArray = len(inputArray) - 1
    indexOfKey = binarySearch(inputArray, lenOfArray, 15)
    if indexOfKey == 0:
        print("fail to find key!")
    else:
        print("index of key is:", indexOfKey)

程序运行结果

# binarySearch0823_1 递归实现

def binarySearch(inputArray, low, high, key):
    # low high mid
    if low <= high :
        mid = low + (high - low) // 2
        if inputArray[mid] > key:
            return binarySearch(inputArray, low, mid - 1, key)
        elif inputArray[mid] < key:
            return binarySearch(inputArray, mid + 1, high, key)
        else:
            return mid
    return 0

if __name__ == "__main__":
    inputArray = [0, 1, 2, 3, 5, 12, 12, 12, 15, 29, 55] #其中，下标为0的位置不参与查找
    lenOfArray = len(inputArray) - 1
    indexOfKey = binarySearch(inputArray, 1, lenOfArray, 15)
    if indexOfKey == 0:
        print("fail to find key!")
    else:
        print("index of key is:", indexOfKey)

程序运行结果

最好时间复杂度: O(1)---在第一个中间位置就找到key
最坏时间复杂度：O(log2^n+1) = O(log2^n) ---一直查找到二叉树的叶子节点才找到或者遍历到叶子节点发现无记录

3. 哈希表查找

无论是顺序表查找，还是二分查找，都需要使用待查找关键字key与数组元素比较，然后一步步缩小查找范围，从而查找到key。哈希表查找避免了“比较”的步骤，可以直接通过关键字key得到待查找记录的内存存储位置（即下标）。

关键字k与记录的存储位置之间的对应关系称为散列函数（又称哈希函数）。利用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。

散列技术既是一种存储方法，也是一种查找方法。散列技术的记录之间不存在逻辑关系，记录只与关键字有关系。

常用的几种散列函数构造方法：
1). 直接定址法。散列函数为线性函数 hash = a * key + b (a, b为常数) --适合查找表较小且连续的情况
2). 数字分析法。抽取关键字的一部分来计算散列存储位置 --适合于关键字位数比较大的情况
3). 平方取中法。 对关键字取平方，并抽取中间n位作为散列地址 --适合于不知道关键字分布，且位数不是很大的情况
4). 折叠法。将关键字从左到右分割成位数相等的几部分（若最后面一部分位数不够可以与其他位数不相等），然后将这几部分叠加求和，并按照散列表表长，取后几位作为散列地址。 --适合关键字位数比较大的情况
5). 除留余数法。f(key) = key mod p (p <= m), m为散列表长
6). 随机数法。--若关键字长度不等，可采用此方法

若两个关键字key1 != key2, 而通过上面的散列函数构造方法得到的f(key1) == f(key2)，即发生了冲突，此时key1, key2称为散列函数的同义词，那么可以采用以下方法来处理冲突。
1). 开放定址法。一旦发生了冲突，就去寻找下一个空的散列地址。即：fi(key) = (f(key) + di) mod m (di = 1,2,3,...,m-1); 其中fi(key)是处理冲突后，给关键字key赋予的空散列地址。f(key)是通过上面六种构造方法计算得到的散列地址。 m为散列表表长。
2). 再散列函数法。事先准备多个散列函数，每当有散列地址冲突时，就换一个散列函数计算。
3). 链地址法。将所有关键字为同义词的记录存储在一个单链表里，单链表称为同义词子表，散列表中只存储所有同义词子表的头指针。
4). 公共溢出区法。为所有冲突的关键字建立一个公共溢出区存放。查找时，对于给定关键字key，先通过散列函数计算出散列地址，与基本表相应位置比对，若相等则查找成功；若不相等，则到溢出表按顺序查找。

代码

#hashSearch.py

#使用除留余数法实现的哈希函数
def hash(key, hashLen):
    return key % hashLen

#插入关键字进散列表
def insertHash(hashTable, hashLen, key):
    hashAddr = hash(key, hashLen) #通过哈希函数求散列地址
    #如果字典hashTable中的key已经存在，说明发生了冲突，这里采用开放寻址法解决冲突
    while hashTable.get(hashAddr):
        hashAddr += 1
        hashAddr = hash(hashAddr, hashLen) #开放地址法解决冲突：f1(key) = (f(key) + di) % hashLen
    hashTable[hashAddr] = key

#从散列表中查询关键字key
def searchHash(hashTable, hashLen, key):
    hashAddr = hash(key, hashLen)
    # 若字典hashTable中的key已经存在并且key对应的value与待查询关键字key不相等，说明发生了冲突，同样采用开放地址法解决冲突
    while hashTable.get(hashAddr) and hashTable[hashAddr] != key:
        hashAddr += 1
        hashAddr = hash(hashAddr, hashLen)
    if hashTable.get(hashAddr) == None:
        return None
    return hashAddr

if __name__ == "__main__":
    hashLen = 20
    L = [13, 29, 27, 28, 26, 30, 38]
    hashTable = {}
    for i in L:
        insertHash(hashTable, hashLen, i)
    searchResult = searchHash(hashTable, hashLen, 13)
    if searchResult == None:
        print("no this record!")
    else:
        print("index of key is:",searchResult)

程序运行结果，由于13 % 20 = 13，因此，13的散列地址为13

若没有·冲突，则散列查找时间复杂度为O(1). 不管记录数n有多大，总可以选择一个合适的装填因子(装填因子 = 填入表中的记录个数/散列表长度)，将平均查找长度限定在某一个范围内，此时散列查找的时间复杂度即可一直保持在O(1).

4. 二叉排序树查找

5. 平衡二叉树(AVL树)查找

6. 多路查找树(B树)查找

这三个有关于树的查找，参考另一篇文章：完全二叉树 平衡二叉树 二叉查找树 B树 B+树