你的位置:Python学习 >> 资讯 >> 深入学习 >> 详细内容 在线投稿

利用Python巧妙实现折半查找算法

热度577票  浏览70次 时间:2011年7月19日 10:15
Python学习\azvt;C

# -*- coding:utf8 -*-Python学习*Fc!tfhq5y7ga\

Bv5V+aNb0import osPython学习!p3htDX&w9L+r`"h

Python学习T1R2At`'@rT

import sysPython学习WS#?!~?V5RG

Python学习*C)PZMn8H K{

import mathPython学习7i X EmD8GhM)v

Python学习MbU3z }G9g:SG

def halfSearch(arr=[1,2,3,4,5],find = 1):

m(@.^ ](a(K0 Python学习J7JiMXIW)k

'''''

~)w3w,GF)LBw0

n|I|t{x0折半查找,2分查找

(U+x3]PA;k&B0 Python学习H'_\6mZ(_9Bz p ]

折半查找的前提是数据是有序的Python学习-pfB,EQ@*n|

/|t!h8rY#x8z0算法:mid = Math.floor(low+hight/2)

Tkn@ }B0S1`0

&yuC-ak0'''

@S;|"b3v \:j;oMmH0 Python学习6r!y{)L0ZAyH/g`

mid = 0Python学习 |GZ/e~hg$b

g0GI t#R~8Vf i0low = 0

V3I \}6tY0 Python学习 I+|Y/r @ s;H5r/A%@)R

high = len(arr) - 1

4A2WEJ$b([3n?8L0

V2b s$\C\m+S0while(low<=high):

sTM_ Dz{0 Python学习uZ"AK5w%N

print low,high

(j\6j&WE^(U8J$v0 Python学习;i9U/V5W[[]u

mid = (low + high)/2

{9Os8G2u0

\u4Yw&H0Rk'|0print midPython学习ut(\ f7b$B3`9b

s+@|.X'Yd(~*D0if(arr[mid]==find):Python学习;~,M+\:U B'^{

Python学习[+xw.?eW;j#HaU

print "find %s index is %s",(find,mid)Python学习 d5J:k;s"Hc%y

Python学习 ph|i X v

return

dY1uz A/d\/V"a,f0 Python学习NcTnMH

else:

V"K+vB1?0 Python学习ER:U'[\D(D&n+p6B

if(find > arr[mid]):Python学习 R/S0Qwmg'^%IBA

f,FUu8D*d0low = mid + 1Python学习DO/NEN;i\lN4W

#EOI GVt%yp0else:Python学习*teC0Kqa(f_TR

Python学习M-}H(lJ AU(CR+M

high = mid - 1

)K Y Oz m.C0

lt%ZQH*eh!tm0print "Not Find"

~HD2U kw0 Python学习'}1E _$P]Z~

return NonePython学习0Natv?q#l,MR fn

l5ZD0}_ e0#运行脚本

q}0@"u}jd"s0

8D4|r,O['Q6@0if __name__ =="__main__":Python学习D7gK,W?.eC-x#{d

^0C"d!V.Z3|l0halfSearch()

Yt'kS/k{ {!oC0
顶:29 踩:33
对本文中的事件或人物打分:
当前平均分:-0.15 (185次打分)
对本篇资讯内容的质量打分:
当前平均分:-0.31 (171次打分)
【已经有159人表态】
26票
感动
23票
路过
13票
高兴
20票
难过
13票
搞笑
19票
愤怒
20票
无聊
25票
同情
上一篇 下一篇