用Python实现的二分查找算法

先来看个用Python实现的二分查找算法实例

#!/usr/bin/envpython
importsys

defsearch2(a,m):
low=0
high=len(a)-1
while(low<=high):
mid=(low+high)/2
midval=a[mid]

ifmidval<m:
low=mid+1
elifmidval>m:
high=mid-1
else:
printmid
returnmid
print-1
return-1

if__name__=="__main__":
a=[int(i)foriinlist(sys.argv[1])]
m=int(sys.argv[2])
search2(a,m)

运行:

administrator@ubuntu:~/Python$pythontest_search2.py1234567894

注:

1.'__'：由于python的类成员都是公有、公开的被存取public，缺少像正统面向对象语言的私有private属性。

于是就用__来将就一下，模拟私有属性。这些__属性往往是内部使用，通常情况下不用改写。也不用读取。

加上2个下划线的目的，一是不和普通公有属性重名冲突，二是不让对象的使用者(非开发者)随意使用。

2.__name__ == "__main__"表示程序脚本是直接被执行的.

如果不等于表示脚本是被其他程序用import引入的.则其__name__属性被设为模块名

Python采用二分查找找出数字的下标

要考虑有重复数字的情况

classSolution(object):
defsearchRange(self,nums,target):
"""
:typenums:List[int]
:typetarget:int
:rtype:List[int]
"""
defbinary_search(start,end,value):
whileend>=start:
mid=(start+end)//2
print(mid)
ifnums[mid]>target:
end=mid-1
elifnums[mid]<target:start="mid+1"else:=""if=""value="=-1:"mid-1="">=startandnums[mid+value]==target:
end=mid+value
else:
returnmid
else:
ifmid+1<=endandnums[mid+value]==target:
start=mid+value
else:
returnmid

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:>

二分算法的定义不在多说了

importsys
source=[1,2,3,4,5,6,7,8,9,10]#mustbeinorder
des=int(sys.argv[1])
low=0
high=len(source)-1
targetIndex=-1
print"des=",des
whilelow<=high:
middle=(low+high)/2
ifdes==source[middle]:
targetIndex=middle
break
elifdes<source[middle]:
high=middle-1
print"middleelement[index=",middle,",value=",source[middle],"]isbiggerthandes,continuesearchfrom[",low,"to",high,"]"
else:
low=middle+1
print"middleelement[index=",middle,",value=",source[middle],"]issmallerthandes,continuesearchfrom[",low,"to",high,"]"
print"searchcomplete,targetelement'sindexinsourcelistis",targetIndex

最后在分享一个

'fileName--BinarySearch.py'

src=[]

defBinarySearch(low,high,target,*src):
'二分查找'
whilelow<=high:
mid=(low+high)//2
midVal=src[mid]
iftarget<midVal:
high=mid-1
eliftarget>midVal:
low=mid+1
else:
returnmid
BinarySearch(low,high,target,*src)

print('Pleaseinput10number:')
fornumberinrange(10):
src.append(int(input('Num%d:'%number)))

sortList=tuple(src)
key=int(input('Pleaseinputkey:'))
location=BinarySearch(0,len(src)-1,key,*sortList)

iflocation!=None:
print('Findtargetat%d'%(location+1))
else:
print('Notarget!')