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
投稿猜你喜欢
- 前言我们在分析列表数据时，常常需要对列表数据进行输出或多列表关联拼接。直接使用列表，列表中的各元素以逗号分隔，每个元素包含引号。如何连接列表
- 刷新本地缓存Ctrl+Shift+R查询select *from [table]修改1、普通更新UPDATE [table] set [字段
- 说明1、字典运算中的键必须是不可变类型，如整数(int)、浮点数(float)、字符串(str)、元组(tuple)等。2、列表(list)
- 在我们平常的开发中可能会遇到这样的问题，就是判断某一列是否全部由数字组成，我们都知道oracle并没有给我们提供这样一个现成的函数，那么根据
- Python内置函数1. classmethod、staticmethod、property 。上述三个内置函数在文章（Python进阶——
网络爬虫抓取特定网站网页的html数据，但是一个网站有上千上万条数据，我们不可能知道网站网页的url地址，所以，要有个技巧去抓取网站的所有h- Excel是微软办公套装软件的一个重要的组成部分，它可以进行各种数据的处理、统计分析和辅助决策操作，广泛地应用于管理、统计财经、金融等众多领
- 本文实例讲述了python实现给微信公众号发送消息的方法。分享给大家供大家参考，具体如下：现在通过发微信公众号信息来做消息通知和告警已经很普
- 前言最近发现一个神器，那就是GitHub和OpenAI联合构建的AI自动编程工具Copilot！Copilot基于自然语言处理模型GPT-3
- Oracle的逻辑运算符也是用在SQL语句中必不可少的因素，一共有三个逻辑运算符意义and双值运算符，如果左右两个条件都为真，则得到的值就为
- jieba.cut与jieba.lcut的区别jieba.cut生成的是一个生成器，generator，也就是可以通过for循环来取里面的每
- 本文实例讲述了CentOS7安装mysql5.7解压缩版的方法。分享给大家供大家参考，具体如下：1.下载安装包http://dev.mysq
- 目录简介开发工具实现代码爬取效果Github地址：简介使用Python Tkinter开发一个爬取B站直播弹幕的工具，启动后在弹窗中输入房间
- 1.基本函数介绍（1）标准类型函数[type()、str()和 cmp()] &n
- 现在获取数组中最大最小值用的越来越多了，于是乎我编了个方法供大家使用。代码如下，若有问题可以与我联系，咱们一起学习一起进步。我们来看下示例一
- 使用pyaudio录音和格式转化环境pip3 install pyaudiopip3 install wavepip3 install nu
- 1.由于设置了slave的配置信息，mysql在数据库data目录下生成master.info,所以如有要修改相关slave的配置要先删除该
- 在深度学习中,模型的输入size通常是正方形尺寸的,比如300 x 300这样．直接resize的话，会把图像拉的变形．通常我们希望resi
- 本文实例讲述了Django框架表单操作。分享给大家供大家参考，具体如下：HTML表单是网站交互性的经典方式。 开始学习如何用Django对用
- 本文实例讲述了python通过smpt发送邮件的方法。分享给大家供大家参考。具体实现方法如下：import smtplib, socketf
