Python 语言实现六大查找算法

下面是关于“Python语言实现六大查找算法”的完整攻略。

1. 六大查找算法

六大查找算法是指顺序查找、二分查找、插值查找、斐波那契查找、树表查找和哈希查找这六种常用的查找算法。这些算法是计算机科学中最基本的算法之一,也是Python开发者必须掌握的算法之一。

2. 算法实现

下面是使用Python实现六大查找算法的完整代码。

2.1 顺序查找

def sequential_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

2.2 二分查找

def binary_search(arr, x):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

2.3 插值查找

def interpolation_search(arr, x):
    low, high = 0, len(arr) - 1
    while low <= high and x >= arr[low] and x <= arr[high]:
        pos = low + int(((float(high - low) / (arr[high] - arr[low])) * (x - arr[low])))
        if arr[pos] == x:
            return pos
        if arr[pos] < x:
            low = pos + 1
        else:
            high = pos - 1
    return -1

2.4 斐波那契查找

def fibonacci_search(arr, x):
    fib2, fib1 = 0, 1
    while fib1 < len(arr):
        fib2, fib1 = fib1, fib2 + fib1
    offset = -1
    while fib1 > 1:
        i = min(offset + fib2, len(arr) - 1)
        if arr[i] < x:
            fib1, fib2 = fib2, fib1 - fib2
            offset = i
        elif arr[i] > x:
            fib1, fib2 = fib - fib2, fib2
        else:
            return i
    if fib1 == 1 and arr[offset + 1] == x:
        return offset + 1
    return -1

2.5 树表查找

class Node:
    def __init__(self, val=None):
        self.left = None
        self.right = None
        self.val = val

def tree_search(root, x):
    if not root:
        return None
    if root.val == x:
        return root
    elif root.val > x:
        return tree_search(root.left, x)
    else:
        return tree_search(root.right, x)

2.6 哈希查找

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]

    def hash_func(self, x):
        return x % self.size

    def insert(self, x):
        hash_val = self.hash_func(x)
        self.table[hash_val].append(x)

    def search(self, x):
        hash_val = self.hash_func(x)
        if x in self.table[hash_val]:
            return True
        else:
            return False

3. 示例

下面是两个查找算法的示例,分别展示了二分查找和哈希查找的实现。

3.1 二分查找示例

arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, x)
if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")

输出:

Element is present at index 3

3.2 哈希查找示例

hash_table = HashTable()
hash_table.insert(5)
hash_table.insert(10)
hash_table.insert(15)
print(hash_table.search(10))
print(hash_table.search(20))

输出:

True
False

4. 总结

六大查找算法是计算机科学中最基本的算法之一,也是Python开发者必须掌握的算法之一。在Python中,我们可以使用各种数据结构和算法来实现这些基本算法。在实际应用中,我们可以根据具体问题选择适当的算法来进行开发和实现。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Python 语言实现六大查找算法 - Python技术站

(0)
上一篇 2023年5月13日
下一篇 2023年5月13日

相关文章

  • Python实现简单层次聚类算法以及可视化

    Python实现简单层次聚类算法以及可视化 层次聚类是一种常用的聚类算法,它可以将数据集分成不同的层结构。本文中,我们将介绍如何使用Python实现简单层次聚类法以及可视化。我们将分为以下几个步骤: 加载数据集 数据预处理 定义层次聚类法 可视化聚类结果 示例说明 步骤1:加载数据集 在实现层次聚类算法之前,需要加载数据集。在这个例子中,我们将使用Iris数…

    python 2023年5月14日
    00
  • Python requests lib 花费的时间比它应该做的 get 请求要长

    【问题标题】:Python requests lib is taking way longer than it should to do a get requestPython requests lib 花费的时间比它应该做的 get 请求要长 【发布时间】:2023-04-03 08:23:01 【问题描述】: 所以我有这个代码。每当我运行代码并到达第 3…

    Python开发 2023年4月8日
    00
  • 10个python爬虫入门实例(小结)

    下面详细讲解一下“10个python爬虫入门实例(小结)”这篇文章的攻略。 文章概述 该文章是一篇教学性质的文章,主要介绍了10个Python爬虫的入门实例,内容涵盖了网络爬虫的基础知识、常用工具和技巧等。该文章共分为10个小节,每个小节介绍了一个不同的Python爬虫实例。 攻略分析 该篇文章的攻略可以分为以下几个步骤: 确定学习目标:想要学习爬虫的哪些知…

    python 2023年5月14日
    00
  • python–pip–安装超时的解决方案

    Python 是目前最流行的编程语言之一,它在数据科学、Web 开发和自动化测试等领域都有着重要的应用。pip 是 Python 的包管理器,它用于安装、升级和管理 Python 的各类库、框架等资源。然而,由于 pip 下载资源的过程经常会出现网络不稳定,甚至安装超时的问题,这就需要我们采取一些解决方案来解决这个问题。 问题描述 如果你使用 pip 安装 …

    python 2023年5月14日
    00
  • 用Python编写个解释器实现方法接受

    下面是用Python编写个解释器实现方法接受的完整攻略: 确认需求和解释器类型 首先,我们需要明确编写解释器的目的和需要解析的语言类型。针对不同的需求,可以选择不同的解释器类型,比如基于抽象语法树(AST)的解释器、基于递归下降分析的解释器或者基于正则表达式的解释器等。 确认解析规则和语法 在开始编写解释器之前,需要明确需要解析的语言的语法规则,这需要花费一…

    python 2023年6月6日
    00
  • Python 生成器表达式

    生成器表达式是python中非常重要的概念,可以用来快速生成集合中的元素而无需占用大量内存,是处理大数据集的必备工具。下面分别从生成器表达式的定义、语法和示例详细讲解Python 生成器表达式的使用方法: 定义 Python生成器表达式是一种用来生成可迭代对象(推荐是迭代器)的简洁便捷的方法,可以在创建数据集时使用,而无需一开始将整个集合装入内存中。当使用生…

    python-answer 2023年3月25日
    00
  • 推荐8款常用的Python GUI图形界面开发框架

    下面我给您详细讲解如何使用8款常用的Python GUI图形界面开发框架。 1. Tkinter Tkinter 是 Python 的标准 GUI 库,因此不需要安装任何其他的包就可以使用。Tkinter 提供了一个简单的方式创建基本的 GUI 应用程序,它包括了一系列的控件,如文本框、按钮、标签和列表框等。 以下是一个简单的 Tkinter 示例程序,在屏…

    python 2023年5月30日
    00
  • PHP中迭代器的简单实现及Yii框架中的迭代器实现方法示例

    PHP中的迭代器是一种用于遍历数据集合的机制。通过实现迭代器接口,我们可以将一个对象转换成一个可迭代的集合,从而可以通过foreach遍历其内容。 在PHP中,一个简单的迭代器实现需要定义以下5个方法: current():返回集合当前位置的元素。 key():返回集合当前位置的键。 next():将集合向前移动一个元素。 rewind():将集合倒回到第一…

    python 2023年6月3日
    00
合作推广
合作推广
分享本页
返回顶部