python算法技巧——搜寻算法训练及讲解

一. 顺序搜寻

        顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。顺序查找的基本原理是对于任意一个序列以及一个给定的元素，将给定元素与序列中元素依次比较，直到找出与给定关键字相同的元素，或者将序列中的元素与其都比较完为止。

1.1 代码如下：

# 顺序搜寻-----------------------------------------------------------
def sequential_search(nlist,key):
    for i in range(len(nlist)):
        if nlist[i]==key:
            return i
    return -1

data = [3,8,5,9,1,4,2,6,7]
key = eval(input('搜寻值为：'))
index = sequential_search(data,key)
if index != -1:
    print('在',index,'索引位置找到了。\n共找了',index+1,'次。')
else:
    print('查无此搜寻字数！')

1.2 算法分析

        找寻过程中很困会需要找寻n次，平均是找寻n/2次，时间复杂度是O(n)。

---

二. 二分搜寻法

        要执行二分搜寻法（binary search），首先要将数据排序，然后将搜寻值（key）与中间值比较，如果搜寻值大于中间值，则下一次往右边（较大值边）搜寻，否则往左边（较小值边）搜寻。上述动作持续进行，直到找到搜寻值或是所有数据搜寻结束才停止。

2.1 代码如下：

# 二分搜寻法（binary search）-----------------------------------------------------------
def binary_search(nlist, key):
    print('搜寻列表为：', nlist)
    low = 0
    high = len(nlist)-1
    middle = int((low+high)/2)
    times = 0
    while True:
        times += 1
        if key == nlist[middle]:
            rtn = middle
            break
        elif key >nlist[middle]:
            low = middle+1
        else:
            high = middle-1
        middle = int((low+high)/2)
        if low > high:
            rtn = -1
            break
    return rtn, times

data = [3,8,5,9,1,4,2,6,7]
data.sort()
key = eval(input('搜寻值为：'))
index,times = binary_search(data,key)
if index != -1:
    print('在',index,'索引位置找到了。\n共找了',times,'次。')
else:
    print('查无此搜寻字数！')

 2.2 算法分析

        每次搜寻可以让搜寻范围减半，当搜寻log n 次时，搜寻范围就剩下一个数据，此时可以判断所搜寻的数据是否存在，所以搜寻的时间复杂度为O(log n)。