Python有序查找算法之二分法实例分析
作者:叮了咣当 发布时间:2023-04-09 00:02:37
标签:Python,二分法,查找算法
本文实例讲述了Python有序查找算法之二分法。分享给大家供大家参考,具体如下:
二分法是一种快速查找的方法,时间复杂度低,逻辑简单易懂,总的来说就是不断的除以2除以2...
例如需要查找有序数组arr里面的某个关键字key的位置,那么首先确认arr的中位数或者中点center,下面分为三种情况:
① 假如arr[center]>key,说明key在arr中心左边范围;
② 假如arr[center]<key,说明key在arr中心右边范围;
③ 假如arr[center]=key,说明key在arr中心。
范围每次缩小一半,写个while的死循环知道找到为止。
二分法查找非常快且非常常用,但是唯一要求是要求数组是有序的
前面一篇冒泡排序可以去看看:
https://www.jb51.net/article/130288.htm
二分法的代码如下:
# -*- coding: utf-8 -*-
def BinarySearch(arr, key):
# 记录数组的最高位和最低位
min = 0
max = len(arr) - 1
if key in arr:
# 建立一个死循环,直到找到key
while True:
# 得到中位数
# 这里一定要加int,防止列表是偶数的时候出现浮点数据
center = int((min + max) / 2)
# key在数组左边
if arr[center] > key:
max = center - 1
# key在数组右边
elif arr[center] < key:
min = center + 1
# key在数组中间
elif arr[center] == key:
print(str(key) + "在数组里面的第" + str(center) + "个位置")
return arr[center]
else:
print("没有该数字!")
if __name__ == "__main__":
print("脚本之家测试结果:")
arr = [1, 6, 9, 15, 26, 38, 49, 57, 63, 77, 81, 93]
while True:
key = raw_input("请输入你要查找的数字:")
if key == " ":
print("谢谢使用!")
break
else:
BinarySearch(arr, int(key))
运行结果:
希望本文所述对大家Python程序设计有所帮助。
来源:https://www.cnblogs.com/bfyin/p/6404173.html
0
投稿
猜你喜欢
- 投资有风险,选择需谨慎。 股票交易数据分析可直观股市走向,对于如何把握股票行情,快速解读股票交易数据有不可替代的作用!1 数据预处
- 【OpenCV】⚠️高手勿入! 半小时学会基本操作 ⚠️ 对象测量概述OpenCV 是一个跨平台的计算机视觉库, 支持多语言, 功能强大.
- 需要在 ~/.pip/pip.conf 配置文件中加入下面的语句,避免这类警告:没有目录或没有配置文件需要自己新建mkdir ~/.pip/
- 本文为大家分享了pygame游戏之旅的第9篇,供大家参考,具体内容如下在游戏开始之前定义一个函数,用来显示游戏介绍:def game_int
- 生成HTML方法主要步骤只有两个:一、获取要生成的html文件的内容二、将获取的html文件内容保存为html文件我在这里主要说明的只是第一
- WEB开发者不光要解决程序的效率问题,对数据库的快速访问和相应也是一个大问题。希望本文能对大家掌握MySQL优化技巧有所帮助。1. 优化你的
- 本文介绍了prototype.js常用函数及其使用方法例子说明函数名
- 目录什么是异常?异常处理try-except 格式一-try...except...格式二-try...except {error
- 任何语言都离不开字符,那就会涉及对字符的操作,尤其是脚本语言更是频繁,不管是生产环境还是面试考验都要面对字符串的操作。python的字符串操
- 用 ASP (using jscript) 在服务端创建 GUID 的代码如下:function GUID(){ ret
- Jira提供了完善的RESTful API,如果不想直接请求API接口可以使用Python的Jira库来操作JiraJira Python文
- 在实际工作中,有时候需要对判断字符串是否为合法的json格式解决方法使用json.loads,这样更加符合‘Pythonic'写法代
- 函数名称:CheckForm_JS(frmName,errStr)功能:用ASP的方法动态写出JavaScript的表单验证的函数check
- 这里列出了13种实现图片或网页内容 lightbox 效果的方法,大部分是链接到各种lightbox作者的英文页面,里面都有源代码下载。Th
- 大家在用asp开发程序的时候,有时候会碰到以下的错误提示:Active Server Pages 错误 'ASP 0141'
- 各大著名厂家、公司的banner广告设计欣赏,尺寸468x60,gif格式!有acer,阿尔卡特,AMD,中国电信,爱立信,Greatwal
- 序言本文所提及的VTD-XML并非本文作者原创,作者只是对它进行介绍。问题通常当我们提起XML的使用时,最头痛的部分便是XML的verbos
- 实战场景初学 Python 爬虫,十之八九大家采集的目标是网页,因此快速定位到网页内容,就成为我们面临的第一道障碍,本篇博客就为你详细说明最
- 写在前面周日下午在家学习,看到一个关于切片的问题,在网上找了一些资料,做个总结。上代码func main() {sl := make([]i
- 题目:用 JavaScript 代码实现空位补零,比如 pad(12, 3) => 012实现一:/* 平淡无奇法 */functio