Python语言实现二分法查找
作者:五包辣条! 发布时间:2021-12-01 18:39:49
标签:Python,二分法,查找
前言:
二分法也就是二分查找,它是一种效率较高的查找方法
假如公司新来了一个人,叫张三,他是你们公司第47个人,过了一段时间后,有些人呢看张三不爽,离职了,那这时候张三肯定不是公司第47个人了,怎么样才知道张三排第几呢,下面我们用二分法把他找出来
思路:
给你一本1000页的书籍,随机给定一个页码,如何用最快的方式找到它?如果一页一页逐步去查找,则最高需要查找一千次!那我们如何用二分法来解决这个问题呢?二分法的关键就是二分这个词。
步骤1:设定一个页码作为中心点来将1000页分为两份,中位数的作用就是每次缩小一半查找范围,即达到开方的效果。即可以用 (首位+末位)/2 = 中位数。
步骤2:将需要查找的页码与中位数比价,如果大于中位数则舍弃对中位数的前一半查找,反之则舍弃对后一半范围查找,达成开方效果。 步骤3:在新的查找范围重新计算出中位数
步骤4:查找页码对比中位数,确定新的查找范围
步骤5:循环以上步骤,直到找到该页码为止
代码:
通过以上思路解析,我们知道了二分法实行步骤,接下来就通过代码来实现步骤,首先是循环实现
#模拟页码
array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
#首位值
low = 0
#末位值
height = len(array)-1
#设定查找页码
findNum = 1
#循环查找
while True:
#获取中位数
mid = int((low+height)/2)
#打印中位数,查看循环次数
print(array[mid])
#如果中位数小于查找值,则锁定后半段
if array[mid] < findNum:
#重置低位数
low = mid + 1
#如果中位数大于查找值,则锁定前半段
elif array[mid] > findNum:
#重置高位值
height = mid - 1
#找到数字则打印该值下标,终止循环
elif array[mid]==findNum:
print('find it:',array[mid],' index:',mid)
break
除了上述方式外,也可以使用递归来实现,代码更加简洁
array = [1, 3, 4, 6, 7, 8, 9, 11, 15, 17, 19, 21, 22, 25, 29, 33, 38, 69,99,107]
#函数递归
#定义一个函数,给三个形参:低位值,高位值,查找值
def BinarySearch(low,height,findNum):
#计算出中位数
middle = (low+height)//2
#如果中位数小于查找值,则锁定后半段
if findNum >array[middle]:
#重置低位数
low = middle +1
#如果中位数大于查找值,则锁定前半段
elif findNum<array[middle]:
#重置高位值
height = middle - 1
else:
#找到该值并返回
return '该值下标为:%s,值为:%s'%(middle,array[middle])
#没有找到则调用自身继续查找
return BinarySearch(low,height,findNum)
print(BinarySearch(array[0],len(array)-1,19))
总结:
根据结果反馈,使用二分法常规Python检索用循环方式找数字21,他是排在11位,中位数查询3次,使用Python二分法检索递归方式先取查询数字的倍数,然后锁定前半段进行索引,索引的步骤耗时更少
来源:https://blog.csdn.net/AI19970205/article/details/123464424
0
投稿
猜你喜欢
- 学Python中,自我感觉学的还不错的亚子~想做点什么来练练手,然后我疯狂的找各种小游戏的教程源码什么的,于是我就疯狂的找呀找呀,就找到了一
- 导言作为web开发人员,我们的生活围绕着数据操作。我们建立数据库来存储数据,写编码来访问和修改数据,设计网页来采集和汇总数据。本文是研究在A
- MySQL是一个真正的多用户、多线程SQL数据库服务器。MySQL是以一个客户机/服务器结构的实现,它由一个服务器守护程序mys
- 不夸张地说,XML正在接管这个世界,正在成为今天一切Web服务和大多数SOA的基础。XML本身并非一种技术,而是程序设计语言,可支持开发者为
- 这主要是因为杀毒软件将一些asp关键词当作木马特征,记录保存着,所以遇到有这个关键词,就会禁止运行或删除。解决的方法是将这些关键词给拆开。把
- 在ASP.NET中,如何连接 SQLServer数据库?连接数据库:<%@ Import Namespace=&q
- 最近重新温习了一次《javascript设计模式》,确实是一本好书,每次看都有不同的领悟,每次领悟到的都受益匪浅,无怪古圣人都说学无止镜了,
- 这篇文章我们学习 Python 变量与数据类型变量变量来源于数学,是计算机语言中能储存计算结果或能表示值抽象概念,变量可以通过变量名访问。在
- 1、检测指定路径下所有文件所占用内存import osdef check_memory(path, style='M'):
- 本文实例讲述了Flask框架模板渲染操作。分享给大家供大家参考,具体如下:from flask import render_template
- 现在公布方法:替换editor.js 函数 // Toolbar button onmouseup
- 笔者日积月累了许多精彩、实用的Web特效的制作,这些特效几乎都是比较常用的网页特效。现在我就把这些经过
- 客户端从服务端下载文件的流程分析: 浏览器发送一个请求,请求访问服务器中的某个网页(如:down.php),该网页的代码如下。 服务器接受到
- 最近对微格式进行了一些学习,在学习过程中收获不少。在此分享下,欢迎交流!微型格式的优点:1,语义化的HTML和CSS类名称来标记共同内容。2
- 如图,这次需要在图片中找到卷尺的红色刻度,所以需要对图像做过滤,只留下红色部分。一开始的想法是分别找到RGB值,然后找到红色区域的部分保留就
- 题目描述1275. 找出井字棋的获胜者 - 力扣(LeetCode)A 和 B 在一个 3 x&nb
- python发起http请求,并解析返回的json字符串的小demo,方便以后用到。#! /usr/bin/env python  
- 首先对空格宽度的定义:空格,由于每个浏览器处理会有微小的不同,在这里我将可以选中的宽度作为空格的宽度。视觉宽度和可选中的宽度有 0~3px
- Matplotlib是一个很好的作图软件,但是python下默认不支持中文,所以需要做一些修改,方法如下:1.在python安装目录的Lib
- 我见朋友可以把数据库的记录显示到列表框里去,挺实用,也想做一个。怎么做啊?这简单,代码和说明如下:dblist.asp<html>