查找算法原理与实现[顺序查找、二分法查找、插值查找、分块查找](python版)

1. 顺序查找

• 原理

顺序查找就是将数列从头到尾按照顺序查找一遍，只需遍历一遍列表，然后逐一判断，顺序查找是最容易理解，时间复杂度最高的排序方法(不需要事先排序)

• 代码实现

# -*- coding:utf-8 -*-

""" 
Author: leadingme
Mail:[email protected]
MyWebsite:leadingme.top
"""

def sequentialSearch(iList,key):

    for i in range(len(iList)):
        if iList[i] == key:
            return i
    return -1

if __name__ == '__main__':
    iList = [7, 5, 9, 3, 5, 1, 12, 10, 15, 9]
    key = 10
    res = sequentialSearch(iList,key)
    print(res)
    if res >= 0:
        print('%d is in the list, index is: %d\n'%(key, res))
    else:
        print('%d is not in list'%key)

2. 二分法查找

• 原理

又称之为折半查找，一种计算复杂度为log(n)的查找方法，与线性查找相比，数量级越大，效率的优势越是明显。但是二分法查找的前提是“已经排序好的线性表”，也就是说，一维数组中的数据必须是已经排序好了，才能使用二分法来进行查找，排序方式没有影响。

• 思路

1：首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。
2：如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤1的操作。
3：如果某一步数组为空，则表示找不到目标元素。

• 代码实现

# -*- coding:utf-8 -*-
""" 
Author: leadingme
Mail:[email protected]
MyWebsite:leadingme.top
"""
from quickSort import quickSort # 从外部导入的快速排序算法

def binarySearch(iList, key):
    iLen = len(iList)
    left = 0   # 初始化左边界下标
    right = iLen - 1  # 初始化右边界下标

    while right > left: # 如果右边结的下标与左边下标相等则跳出循环
        mid = (right+left) // 2
        if key < iList[mid]:   # 如果比中间的数小，则调整右边界为mid-1
            right = mid - 1
        elif key > iList[mid]:  # 如果比中间的数大，则调整左边界mid+1
            left = mid + 1
        else:   # 相等则返回
            return mid
    if key == iList[left]:
        return left
    elif key == iList[right]:
        return right
    else:     # 如果到right > left还没找到，则证明列表中没有改元素
        return -1

if __name__ == '__main__':
    iList = [7, 5, 9, 3, 5, 1, 12, 10, 15, 9]
    iList = quickSort(iList)  # 用快速排序给列表排序
    key = 10
    res = binarySearch(iList, key)
    if res >= 0:
        print('%d is in the list, index is: %d\n' % (key, res))
    else:
        print('%d is not in list' % key)

续更…