Python实现七大查找算法的示例代码

Python实现七大查找算法的示例代码

查找算法是计算机科学中的一个重要问题。本文将介绍Python现七大查找算法的示例代码,包括线性查找、二分查找插值查找、斐波那契查找、树表查找、哈希查找和跳跃表查找。

线性查找

线性查找一种简单的查找算法,适用于小型数据集。该算法从数据集的第一个元素开始,逐个比较每个元素,直到找到标元素或遍历完整个数据。

以下是Python实现线性查找的示例代码:

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

述代码中,定义了一个linear_search函数,接受一个数组arr和目标元素target作为参数。在循环中,逐个比较数组中的元素,如果找到目标元素,则返回其索。如果遍历完整个数组仍未找到目标元素,则返回-1。

二分查找

二分查找是一种高效的查找算法,适用于有序数据集。该算法将集分成两个部分,每次比较中间元素,如果目标元素小于中间元素,则在左半部分继续查找,否则在右半部分查找,直到找到目标素或无法继续分割。

以下是Python实现二分查找的示例代码:

def binary_search(arr, target):
    left, right 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

上述代码中,定义了一个binary_search函数,接受一个有序arr和标元素target作为参数。在循环中,每次将数组分成两个部分,比较中间元素,如果目标元素小于中间元素,则在左半部分继续查找,否则在右半部分查找,直找到目标元素或无法继续分割。如果遍历完整个数组仍未找到目标元素,则返回-1。

示例说明

以下是两个示例,说明如何使用linear_search和binary_search函数查找目标元素。

示例1

使用linear_search函数查找目标元素5。

arr = [1, 3, 5, 7, 9]
target = 5
result = linear_search(arr, target)
if result != -1:
    print(f"目标元素target}在数组中的索引为{result}")
else:
    print(f"目标元素{target}不在数组中")

输出结果```
目标元素5在数组中的索引为2


### 示例2

使用binary_search查找目标元素7。

```python
arr = [1, 3, 5, 7, 9]
target = 7
result = binary_search(arr, target)
if result != -1:
    print(f"目标元素{target}在数组中的索引为{result}")
else:
    print(f目标元素{target}不在数组中")

输出结果:

目标元素7在数组中的索引为3

插值查找

插值查找是一种高效的查找算法,适用于有序数据集。该算法根据标元在数据集中的位置,估算其可能的位置,从而快速定位目标元素。

以下是Python实现插值查找示例代码:

def interpolation_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right and arr[left] <= target <= arr[right]:
        pos = left + (target - arr[left]) * (right - left) // (arr[right] - arr[left])
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    return -1

上述代码中,定义了一个interpolation_search函数接受一个有序数组arr和目标元素target作为参数。在循环中,根据目标元素在数据集中的位置,估算其可能的位置,从而快速定位目标元素。如果找到目标元素,则返回其索引。如果历完整个数组仍找到目标元素,则返回-1。

斐波那契查找

斐波那契查找是一种高效的查找算法,适用于有序数据集该算法利用斐波那契数列的特性,将数据集分成两个部分,每次比较中间元素,如果目标元素小于中间元素,则在左半部分继续查找,否则在右半部分查找,直到找到目标元素或无法继续分割。

以下是Python实现斐波那契查找示例代码:

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

上代码中,定义了一个fib_search函数,接受一个有序数组arr和目标元素target作为参数。在循环中,利用斐波那契数列的特性,将数据分成两个部分,每次比较中间元素,如果目标元素小于中间素,则在左半部分继续查找,否则在右半部分查找,直到找到目标元素或无法继续分割。如果找到目标元素,则返回其索引。如果遍历完整个数组仍未找到目标元素,则返回-1。

树表查找

树表查找是一种高效的查找算法,适用于有序数据集。算法将数据集构建成一棵二叉查找树,每次比较中间节点,如果标元素小于中间节点,则在左子树继续查找,否则在右子树查找,直到找到目标元素或无继续分割。

以下是Python现树表查找的示例代码:

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

def build_tree(arr):
    if not arr:
        return None
    mid = len(arr) // 2
    root = TreeNode(arr[mid])
    root.left = build_tree(arr[:mid])
    root.right = build_tree(arr[mid+1:])
    return root

def tree_search(root, target):
    if not root:
        return -1
    if root.val == target:
        return 0
    elif root.val < target:
        result = tree_search(root.right, target)
        if result == -1:
            return -1
        else:
            return result + 1
    else:
        result = tree_search(root.left, target)
        if result == -1:
            return -1
        else:
            return result + 1

上述代码中,定义了一个TreeNode类表示二叉查找树的节点,包括节点值和左右子树。build_tree函数接受一个有序数组arr为参数,构建一棵二叉查找树。tree_search函数接受一个二叉找树的根节点root和目标元素target作为参数,递归比较中间节点,如果目标元素小于中间节点,则在左子树继续查找,否则在右子树查找,直到找到目标元素或法继续分割。如果找到目标元素,则返回其深度。如果遍历完整个树仍未找到目标元素,则返回-1。

哈希查找

哈希查找是一种效的查找算法,适用于大型数据集。该算法将数据集映射到哈希表中,每次查找时,根据目标元素的哈希值,快速定位其可能的位置,从而快速定位目标元素。

以下是Python实现哈希查找的示例代码:

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

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

    def insert(self, key, value):
        hash_key = self.hash_func(key)
        for i, item in enumerate(self.table[hash_key]):
            if item[0] == key:
                self.table[hash_key][i] = (key, value)
                return
        self.table[hash_key].append((key, value))

    def search(self, key):
        hash_key = self.hash_func(key)
        for item in self.table[hash_key]:
            if item[0] == key:
                return item[1]
        return None

上述代码中,定义了一个HashTable类表示哈希表,包括哈希表大小和哈希表数组。hash_func函数接受一个键值key作为参数,返回其哈希值。insert函数接受一个键值key和值value作为参数,将其插入哈希表中。search函数接受一个键值key作参数,根据其哈希值快速定位其可能的位置,从而快速定位目标元素。如果找到目标元,则返回值。如果遍历完整个哈希表仍未找到目标元素,则返回None。

跳跃表查找

跳跃表查找是一种高效的查找算法,适用于大型数据集。算法将数据集构建成一种特殊的链表,每个节点包含多个指针,可以快速跳过一些节点,从而快速定位目标元素。

以下是Python实现跳跃表查找的示例代码:

import random

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None

class SkipList:
    def __init__(self):
        self.head = Node(-1)
        self.levels = 1

    def insert(self, val):
        level = 1
        while random.random() < 0.5:
            level += 1
        if level > self.levels:
            self.head.next = Node(val)
            for i in range(self.levels, level):
                node = Node(-1)
                node.down = self.head.next
                self.head.next = node
            self.levels = level
        node = self.head.next
        prev = self.head
        for i in range(self.levels - 1, -1, -1):
            while node and node.val < val:
                prev, node = node, node.next
            if i < level:
                new_node = Node(val)
                new_node.next = node
                prev.next = new_node
                new_node.down = down_node
                down_node = new_node
            prev, node = prev.down, node.down

    def search(self, val):
        node = self.head.next
        for i in range(self.levels - 1, -1, -1):
            while node and node.val < val:
                node = node.next
            if node and node.val == val:
                return True
            node = node.down
        return False

上述代码中,定义了一个Node类表示跳跃表的节点,包括节点值、下一个节点和下一层节点。SkipList类表示跳跃表包括头节点和层数。insert函数接受一个值val作为参数,将其插入跳跃表中。search函数接受一个值val作为参数,快速定位目标元素。如果找到目元素,则返回True。如果遍历完整个跳跃表仍未找到目标元素,则False。

总结

本文介绍了Python实现七大查找算法的示例代码,包括线性查找、二分查找、值查找、斐波那契查找、树表查找、哈希查找和跳跃表查找不同的查找算法适用于不同的数据集和场景,需要根据实际情况选择合适的算法。在实际应中,需要注意算法的时间复杂度和空间复杂度,以获得更好的性能。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Python实现七大查找算法的示例代码 - Python技术站

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

相关文章

  • Zookeeper接口kazoo实例解析

    Zookeeper接口kazoo实例解析 Zookeeper是一个分布式协调服务,可以用于管理分布式系统中的配置信息、命名服务、分布式锁等。Kazoo是一个基于Python的Zookeeper客户端库,可以方便地与Zookeeper进行交互。本文将详细讲解Kazoo的安装和使用过程,包括Kazoo的安装、连接Zookeeper、创建节点、获取节点数据等内容,…

    python 2023年5月15日
    00
  • python使用多线程查询数据库的实现示例

    我来为您详细讲解“Python使用多线程查询数据库的实现示例”的完整攻略。 什么是多线程 多线程是指在一个程序中,同时运行多个线程来执行不同的任务。每个线程独立执行自己的任务,但是它们会共享进程中的资源,如内存等。 在 Python 中进行多线程处理,需要使用相关的模块,通常使用 threading 和 concurrent.futures 模块。 多线程查…

    python 2023年5月19日
    00
  • Python实现动态条形图绘制的示例代码

    下面我来给你讲解一下“Python实现动态条形图绘制的示例代码”的完整攻略。 一、背景介绍 Python是一种高级编程语言,一直以来都是数据科学和机器学习领域最受欢迎的语言之一,因为Python有着强大的数据处理和可视化能力。在数据分析的过程中,我们往往需要将数据可视化,特别是通过交互式可视化来更好地展示数据,动态条形图便是一种常见的交互式可视化。 二、实现…

    python 2023年6月3日
    00
  • Python多线程处理实例详解【单进程/多进程】

    Python多线程处理实例详解【单进程/多进程】 什么是多线程? 在操作系统中,进程是分配资源的基本单位,而线程则是进程中执行代码的单位。 一个进程中可以包含多个线程,每个线程共享进程的内存和资源,但是每个线程也有各自的执行堆栈和局部变量,从而实现并发执行。 Python中的多线程实现 Python中使用threading模块实现多线程。 使用Thread类…

    python 2023年5月18日
    00
  • 分享13个好用到起飞的Python技巧

    分享13个好用到起飞的Python技巧攻略 简介 Python是一种高级编程语言,当前在Web开发、数据分析、人工智能等领域广泛应用。在Python编程中,掌握一些技巧对于提高开发效率和编写高质量的代码都十分有帮助。以下是13个好用到起飞的Python技巧攻略。 好用到起飞的技巧 把列表中的元素反转 my_list = [1, 2, 3, 4, 5] my_…

    python 2023年5月30日
    00
  • torch.optim优化算法理解之optim.Adam()解读

    下面是对于“torch.optim优化算法理解之optim.Adam()解读”的完整攻略。 1. 优化算法概述 在神经网络训练的过程中,我们需要选择一个好的优化算法来更新模型中的参数,这个过程就是优化算法。优化算法可以通过最小化损失函数来更新参数,以便更好地拟合数据。 目前常用的优化算法有SGD、Adam、RMSprop等,每个算法都有自己的优缺点,选用不同…

    python 2023年6月6日
    00
  • python常用函数与用法示例

    Python常用函数与用法示例攻略 1. Python常用内置函数 1.1 type()函数 type()函数可以用来查看一个对象的数据类型。 示例: a = ‘Hello World’ b = 123 c = [1, 2, 3] print(type(a)) print(type(b)) print(type(c)) 输出: <class ‘str’…

    python 2023年5月30日
    00
  • python itsdangerous模块的具体使用方法

    Python itsdangerous模块的具体使用方法 Python itsdangerous模块提供了一种生成和验证安全令牌的机制。它可以用来解决一些常见的 Web 安全问题,如用户身份验证、CSRF等。在本文中,我们将深入了解itsdangerous模块的具体使用方法。 安装itsdangerous模块 安装itsdangerous模块非常简单,只需要…

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