Python实现的数据结构与算法之基本搜索详解-Python教程-PHP中文网

首页

后端开发

Python教程

Python实现的数据结构与算法之基本搜索详解

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 10, 2016 pm 03:14 PM

python 搜索数据结构算法

本文实例讲述了Python实现的数据结构与算法之基本搜索。分享给大家供大家参考。具体分析如下：

一、顺序搜索

顺序搜索是最简单直观的搜索方法：从列表开头到末尾，逐个比较待搜索项与列表中的项，直到找到目标项（搜索成功）或者超出搜索范围（搜索失败）。

根据列表中的项是否按顺序排列，可以将列表分为无序列表和有序列表。对于无序列表，超出搜索范围是指越过列表的末尾；对于有序列表，超过搜索范围是指进入列表中大于目标项的区域（发生在目标项小于列表末尾项时）或者指越过列表的末尾（发生在目标项大于列表末尾项时）。

1、无序列表

在无序列表中进行顺序搜索的情况如图所示：

def sequentialSearch(items, target):
  for item in items:
    if item == target:
      return True
  return False

登录后复制

2、有序列表

在有序列表中进行顺序搜索的情况如图所示：

def orderedSequentialSearch(items, target):
  for item in items:
    if item == target:
      return True
    elif item > target:
      break
  return False

登录后复制

二、二分搜索

实际上，上述orderedSequentialSearch算法并没有很好地利用有序列表的特点。

二分搜索充分利用了有序列表的优势，该算法的思路非常巧妙：在原列表中，将目标项（target）与列表中间项（middle）进行对比，如果target等于middle，则搜索成功；如果target小于middle，则在middle的左半列表中继续搜索；如果target大于middle，则在middle的右半列表中继续搜索。

在有序列表中进行二分搜索的情况如图所示：

根据实现方式的不同，二分搜索算法可以分为迭代版本和递归版本两种：

1、迭代版本

def iterativeBinarySearch(items, target):
  first = 0
  last = len(items) - 1
  while first <= last:
    middle = (first + last) // 2
    if target == items[middle]:
      return True
    elif target < items[middle]:
      last = middle - 1
    else:
      first = middle + 1
  return False

登录后复制

2、递归版本

def recursiveBinarySearch(items, target):
  if len(items) == 0:
    return False
  else:
    middle = len(items) // 2
    if target == items[middle]:
      return True
    elif target < items[middle]:
      return recursiveBinarySearch(items[:middle], target)
    else:
      return recursiveBinarySearch(items[middle+1:], target)

登录后复制

三、性能比较

上述搜索算法的时间复杂度如下所示：

搜索算法          时间复杂度
-----------------------------------
sequentialSearch      O(n)
-----------------------------------
orderedSequentialSearch  O(n) 
-----------------------------------
iterativeBinarySearch   O(log n)
-----------------------------------
recursiveBinarySearch   O(log n)
-----------------------------------
in             O(n)

登录后复制

可以看出，二分搜索的性能要优于顺序搜索。

值得注意的是，Python的成员操作符 in 的时间复杂度是O(n)，不难猜出，操作符 in 实际采用的是顺序搜索算法。

四、算法测试

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def test_print(algorithm, listname, target):
  print(' %d is%s in %s' % (target, '' if algorithm(eval(listname), target) else ' not', listname))
if __name__ == '__main__':
  testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
  orderedlist = sorted(testlist)
  print('sequentialSearch:')
  test_print(sequentialSearch, 'testlist', 3)
  test_print(sequentialSearch, 'testlist', 13)
  print('orderedSequentialSearch:')
  test_print(orderedSequentialSearch, 'orderedlist', 3)
  test_print(orderedSequentialSearch, 'orderedlist', 13)
  print('iterativeBinarySearch:')
  test_print(iterativeBinarySearch, 'orderedlist', 3)
  test_print(iterativeBinarySearch, 'orderedlist', 13)
  print('recursiveBinarySearch:')
  test_print(recursiveBinarySearch, 'orderedlist', 3)
  test_print(recursiveBinarySearch, 'orderedlist', 13)

登录后复制

运行结果：

$ python testbasicsearch.py
sequentialSearch:
 3 is not in testlist
 13 is in testlist
orderedSequentialSearch:
 3 is not in orderedlist
 13 is in orderedlist
iterativeBinarySearch:
 3 is not in orderedlist
 13 is in orderedlist
recursiveBinarySearch:
 3 is not in orderedlist
 13 is in orderedlist

登录后复制

希望本文所述对大家的Python程序设计有所帮助。

本站声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

热AI工具

热工具

热门话题

gmail邮箱登陆入口在哪里

7733

Java教程

1643

CakePHP 教程

1397

Laravel 教程

1290

PHP教程

1233

显示更多

Related knowledge

PHP和Python：解释了不同的范例 Apr 18, 2025 am 12:26 AM

PHP主要是过程式编程，但也支持面向对象编程（OOP）；Python支持多种范式，包括OOP、函数式和过程式编程。PHP适合web开发，Python适用于多种应用，如数据分析和机器学习。

在PHP和Python之间进行选择：指南 Apr 18, 2025 am 12:24 AM

PHP适合网页开发和快速原型开发，Python适用于数据科学和机器学习。1.PHP用于动态网页开发，语法简单，适合快速开发。2.Python语法简洁，适用于多领域，库生态系统强大。

Python vs. JavaScript：学习曲线和易用性 Apr 16, 2025 am 12:12 AM

Python更适合初学者，学习曲线平缓，语法简洁；JavaScript适合前端开发，学习曲线较陡，语法灵活。1.Python语法直观，适用于数据科学和后端开发。2.JavaScript灵活，广泛用于前端和服务器端编程。

vs code 可以在 Windows 8 中运行吗 Apr 15, 2025 pm 07:24 PM

VS Code可以在Windows 8上运行，但体验可能不佳。首先确保系统已更新到最新补丁，然后下载与系统架构匹配的VS Code安装包，按照提示安装。安装后，注意某些扩展程序可能与Windows 8不兼容，需要寻找替代扩展或在虚拟机中使用更新的Windows系统。安装必要的扩展，检查是否正常工作。尽管VS Code在Windows 8上可行，但建议升级到更新的Windows系统以获得更好的开发体验和安全保障。

PHP和Python：深入了解他们的历史 Apr 18, 2025 am 12:25 AM

PHP起源于1994年，由RasmusLerdorf开发，最初用于跟踪网站访问者，逐渐演变为服务器端脚本语言，广泛应用于网页开发。Python由GuidovanRossum于1980年代末开发，1991年首次发布，强调代码可读性和简洁性，适用于科学计算、数据分析等领域。

visual studio code 可以用于 python 吗 Apr 15, 2025 pm 08:18 PM

VS Code 可用于编写 Python，并提供许多功能，使其成为开发 Python 应用程序的理想工具。它允许用户：安装 Python 扩展，以获得代码补全、语法高亮和调试等功能。使用调试器逐步跟踪代码，查找和修复错误。集成 Git，进行版本控制。使用代码格式化工具，保持代码一致性。使用 Linting 工具，提前发现潜在问题。