Python如何实现的二分查找算法
作者:Python 发布时间:2021-10-22 18:39:30
标签:Python,二分查找算法
先来看个用Python实现的二分查找算法实例
import sys
def search2(a,m):
low = 0
high = len(a) - 1
while(low <= high):
mid = (low + high)/2
midval = a[mid]
if midval < m:
low = mid + 1
elif midval > m:
high = mid - 1
else:
print mid
return mid
print -1
return -1
if __name__ == "__main__":
a = [int(i) for i in list(sys.argv[1])]
m = int(sys.argv[2])
search2(a,m)om/weixin.html#_labeldown
运行:
administrator@ubuntu:~/Python$ python test_search2.py 123456789 4
注:
1.'__':由于python的类成员都是公有、公开的被存取public,缺少像正统面向对象语言的私有private属性。
于是就用__来将就一下,模拟私有属性。这些__属性往往是内部使用,通常情况下不用改写。也不用读取。
加上2个下划线的目的,一是不和普通公有属性重名冲突,二是不让对象的使用者(非开发者)随意使用。
2.__name__ == "__main__"表示程序脚本是直接被执行的.
如果不等于表示脚本是被其他程序用import引入的.则其__name__属性被设为模块名
Python采用二分查找找出数字的下标
要考虑有重复数字的情况
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
def binary_search(start,end,value):
while end>=start:
mid = (start+end)//2
print(mid)
if nums[mid]>target:
end = mid-1
elif nums[mid]<target: start="mid+1" else:="" if="" value="=-1:" mid-1="">=start and nums[mid+value] == target:
end = mid+value
else:
return mid
else:
if mid+1<=end and nums[mid+value] == target:
start = mid+value
return -1
a=binary_search(0,len(nums)-1,-1)
b=binary_search(0,len(nums)-1,1)
return [a,b]
a = Solution()
l = [2,2]
print(a.searchRange(l,2))
</target:>
二分算法的定义不在多说了
import sys
source = [1,2,3,4,5,6,7,8,9,10] #must be in order
des = int(sys.argv[1])
low = 0
high = len(source) - 1
targetIndex = -1
print "des=",des
while low <= high:
middle = (low + high)/2
if des == source[middle]:
targetIndex = middle
break
elif des < source[middle]:
high = middle -1
print "middle element[index=",middle,",value=",source[middle],"] is bigger than des, continue search from[",low,"to",high,"]"
else:
low = middle + 1
print "middle element[index=",middle,",value=",source[middle],"] is smaller than des, continue search from[",low,"to",high,"]"
print "search complete, target element's index in source list is ",targetIndex
最后在分享一个
'fileName--BinarySearch.py'
src = []
def BinarySearch(low, high, target, *src):
'二分查找'
while low <= high:
mid = (low + high) // 2
midVal = src[mid]
if target < midVal:
high = mid - 1
elif target > midVal:
low = mid + 1
else:
return mid
BinarySearch(low, high, target, *src)
print('Please input 10 number:')
for number in range(10):
src.append(int(input('Num %d:' % number)))
sortList = tuple(src)
key = int(input('Please input key:'))
location = BinarySearch(0, len(src) - 1, key, *sortList)
if location != None:
print('Find target at %d' % (location + 1))
else:
print('No target!')
实例补充
#!/usr/bin/python env
# -*- coding:utf-8 -*-
def half_search(array,target):
low = 0
high = len(array) - 1
while low < high:
mid = (low + high)/2
if array[mid] > target:
high = mid - 1
elif array[mid] < target:
low = mid + 1
elif array[mid] == target:
print 'I find it! It is in the position of:',mid
return mid
else:
print "please contact the coder!"
return -1
if __name__ == "__main__":
array = [1, 2, 2, 4, 4, 5]
运行结果如下:
I find it! It is in the position of: 4
4
-1
I find it! It is in the position of: 0
0
-1
来源:https://www.py.cn/jishu/jichu/10384.html
0
投稿
猜你喜欢
- 前言由与上不了学,教我们Mastercam的老师提前给我们布置了4道习题。对我们太好了,谢谢老师�没办法,干就完了。只是要求附上制作过程视频
- 最近用Python写了个 * ,需要部署到Linux环境的服务器上,由于之前本地开发时使用virtualenv,使用这个虚拟环境有个好处是项目
- 处于兴趣,写了一个遍历指定城市五天内的天气预报,并转为华氏度显示。把城市名字写到一个列表里这样可以方便的添加城市。并附有详细注释import
- ASP木马防御: 代码如下:const adTypeBinary=1 dim jpg(1):jpg(0)=CB
- 通过phpmyadmin连接mysql数据库时提示:“2003 无法登录 MySQL服务器”。。。很明显这是没有启动mysql服务,右击我的
- 安装需要的包1 第一步:全文检索不同于特定字段的模糊查询,使用全文检索的效率更高,并且能够对于中文进行分词处理。haystack:全文检索的
- 说明 1. 状态机是一个非常实用的理论。在涉及到复杂的场景,建立状态机模型,能带来极大的方便。比如,网络连接、模型状态、业务逻辑。
- 学习使用存储过程(Stored Procedure),是ASP程序员的必须课之一。所有的大型数据库都支持存储过程,比如Oracle
- 怎样才能将在表A取得的数据插入另一个表B中?(1)对于表A和表B两个表结构完全相同的话〔字段个数,相应字段的类型等等〕,可以使用 inser
- 详解python中的文件与目录操作一 获得当前路径1、代码1>>>import os>>>print(&
- 本文介绍以下内容:1. 使用transformers框架做预训练的bert-base模型;2. 开发平台使用Google的Colab平台,白
- 1.变量命名1)命名的规范性变量名可以包括字母、数字、下划线,但是数字不能做为开头。系统关键字不能做变量名使用除了下划线之个,其它符号不能做
- 最近做了一个项目,将从微信下载的音频文件(默认为.amr格式)转化为mp3格式(否则前端播放将会遇到困难)上传到云端。经过一番研究,最终决定
- 沟通的时候,一般我不主动说自己是做用户体验设计,也不说做以用户为中心的设计,包括UED, UCD。这种专业名词传达的太虚,你也许是名用户体验
- #!/usr/bin/env python# -*- coding:utf-8-*-# file: {NAME}.py# @author:
- Oracle 的正规表达式的实施是以各种 SQL 函数和一个 WHERE 子句操作符的形式出现的。如果您不熟悉正规表达式,那么这篇文章可以让
- MySQL的ODBC接口实现是通过安装MyODBC驱动,这个驱动程序是跨平台的。如果在Linux等Unix体系操作系统下使用,需要先安装Io
- 如何用HtmlEncode来显示Unicode? 见下:<%@ Language=VBS
- 本文为大家分享了购物商城小程序,供大家参考,具体内容如下软件版本:python3.x功能:实现简单购物商城1.允许用户选择购买多
- 前言python本身使用 \ 来转义一些特殊字符,比如在字符串中加入引号的时候s = 'i\'m superman'