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
3
注:
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: ifvalue==-1: ifmid-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))
二分算法的定义不在多说了，百度一下就知道（支持国产大笑）
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!')