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中的迭代是指重复执行一系列指令的过程。Python通过迭代器来实现迭代。迭代器是一个可以遍历元素的对象,它能被next()函数调用并不断返回下一个值,直到发生StopIteration异常。 迭代器的实现方式 在Python中,我们可以通过定义一个类和实现__iter__()和__next__()方法来创建一个迭代器…

    python 2023年6月6日
    00
  • 用Python生成HTML表格的方法示例

    在Python中,我们可以使用各种库和框架来生成HTML表格。以下是用Python生成HTML表格的方法示例的完整攻略,包含两个示例。 示例1:使用Python内置的字符串格式化生成HTML表格 以下是一个示例,可以使用Python内置的字符串格式化生成HTML表格: 步骤1:定义表格数据 在使用Python内置的字符串格式化生成HTML表格之前,我们需要先…

    python 2023年5月15日
    00
  • pandas读取CSV文件时查看修改各列的数据类型格式

    当我们使用pandas读取CSV文件时,默认会根据每列数据的内容自动判断数据类型。如果数据量较大,或者数据类型较为复杂,那么自动判断可能就存在偏差。在这种情况下,我们可以手动指定每列的数据类型。 下面是如何指定数据类型的具体步骤及示例说明: 步骤1:使用pandas的read_csv函数读取CSV文件,同时指定参数dtype,为每列指定数据类型。 impor…

    python 2023年6月3日
    00
  • Python的函数使用介绍

    让我们开始介绍“Python的函数使用”。 函数的概念 函数是一段可重用的代码块,其可以接收参数、进行处理、并返回一个结果。这种可重用性使得代码更加模块化、可读性更高,且方便调用。Python中的函数使用起来非常方便、灵活,因此在Python开发中函数是非常重要的概念。 函数的定义与调用 Python中定义函数非常简单,在函数名后加括号即可,如下所示: de…

    python 2023年5月31日
    00
  • pip报错“ImportError: cannot import name ‘main’ from ‘pip’ (/usr/lib/python3/dist-packages/pip/init.py)”怎么处理?

    当使用 pip 安装 Python 包时,可能会遇到 “ImportError: cannot import name ‘main’ from ‘pip’ (/usr/lib/python3/dist-packages/pip/init.py)” 错误。这个错误通常是由于 pip 版本不兼容或安装过程中出现问题导致的。以下是详细讲解 pip 报错 “Impo…

    python 2023年5月4日
    00
  • Python pickle类库介绍(对象序列化和反序列化)

    当我们需要在Python程序中,将一个Python对象直接持久化至磁盘中,或是从磁盘中加载一个Python对象时,我们可以使用pickle类库。其实,pickle类库实现的是Python对象的序列化和反序列化。 接下来,我们将会详细讲解pickle类库的一些相关概念、函数的基本使用方法以及示例。 1. 序列化和反序列化 所谓序列化,即是将一个Python对象…

    python 2023年6月2日
    00
  • Python自定义主从分布式架构实例分析

    Python自定义主从分布式架构实例分析 介绍 分布式架构是大规模系统的一种设计模式,由多个独立计算机节点组成,各节点之间进行通讯和协作,并共同解决一个问题。本文将讲解Python实现自定义主从分布式架构的完整攻略,包含以下内容: 主从分布式架构原理 服务端代码实现 客户端代码实现 示例说明 主从分布式架构原理 主从分布式架构是指有一个或多个主服务器节点,其…

    python 2023年6月7日
    00
  • python编程实现12306的一个小爬虫实例

    Python编程实现12306的一个小爬虫实例 爬虫实例介绍 本爬虫实例主要是用Python编写的,通过模拟用户登录和查询车票的方式来获取查询结果。在本实例中,我们将使用requests库和正则表达式来进行实现,最终可以输出符合条件的车票信息。 实现步骤 步骤一:模拟登录 首先,我们需要模拟用户登录。通过F12或其他抓包工具,可以查看12306网站登录时提交…

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