黑马程序员技术交流社区

标题: 【广州Python】Python实现搜索算法 [打印本页]

---

作者: yangrui    时间: 2019-2-21 12:46
标题: 【广州Python】Python实现搜索算法


将数据存储在不同的数据结构中时，搜索是非常基本的必需条件。最简单的方法是遍历数据结构中的每个元素，并将其与您正在搜索的值进行匹配。这就是所谓的线性搜索。它效率低下，很少使用，但为它创建一个程序给出了我们如何实现一些高级搜索算法的想法。
线性搜索
在这种类型的搜索中，逐个搜索所有值。每个值都会被检查，如果找到匹配项，那么返回该特定值，否则搜索将继续到数据结构的末尾。代码如下：

[Python] 纯文本查看 复制代码

def linear_search(data, search_for):

    """线性搜索"""

    search_at = 0

    search_res = False

    while search_at < len(data) and search_res is False:

        if data[search_at] == search_for:

            search_res = True

        else:

            search_at += 1

    return search_res





lis = [5, 10, 7, 35, 12, 26, 41]

print(linear_search(lis, 12))

print(linear_search(lis, 6))

插值搜索
该搜索算法适用于所需值的探测位置。为了使该算法正常工作，数据收集应该以排序形式并平均分布。最初，探针位置是集合中最大项目的位置。如果匹配发生，则返回项目的索引。如果中间项目大于项目，则再次在中间项目右侧的子数组中计算探针位置。否则，该项目将在中间项目左侧的子数组中搜索。这个过程在子数组上继续，直到子数组的大小减小到零。代码如下：

[Python] 纯文本查看 复制代码

def insert_search(data,x):

    """插值搜索"""

    idx0 = 0

    idxn = (len(data) - 1)

    while idx0 <= idxn and x >= data[idx0] and x <= data[idxn]:

        mid = idx0 +int(((float(idxn - idx0)/(data[idxn] - data[idx0])) * (x - data[idx0])))

        if data[mid] == x:

            return "在下标为"+str(mid) + "的位置找到了" + str(x)

        if data[mid] < x:

            idx0 = mid + 1

    return "没有搜索到" + str(x)





lis = [2, 6, 11, 19, 27, 31, 45, 121]

print(insert_search(lis, 31))

print(insert_search(lis, 3))

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2