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

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

热度613票  浏览78次 时间:2011年7月19日 10:15
Python学习F~.P+_+RR

# -*- coding:utf8 -*-Python学习&\7J6v$o(c,??1Y5R

Python学习b6s6v%["o5RB_il

import osPython学习1h6{e{2bh8E0Q%|V

A}{,wf:xL.N0import sysPython学习^9jU g+j9M%~&|h

V.M:vK8v.[b A%x;B0import math

}1ouKKiHX Q-x)d0 Python学习7Z]*J$c LA

def halfSearch(arr=[1,2,3,4,5],find = 1):Python学习 W |8]RAP|(ede

Python学习6cUAM/fz hOu

'''''

i8](C'RZ2f{"\R0

g8@:q f9d~%oWxgD0折半查找,2分查找Python学习 v'g u7pC1DF

Python学习tcE N'{

折半查找的前提是数据是有序的Python学习H!T5{|S-k

Python学习1s1I"Zj1t}R

算法:mid = Math.floor(low+hight/2)

/L x @4m3R!pY0 Python学习$^T,g.Ry(vY%\(|;M

'''

F(q;u.j$`HJ$E}0 Python学习vCgH H

mid = 0Python学习2[|-JNQ/e9g

Python学习nni:E#ot1A

low = 0Python学习} }c9BLO-I1h \

&H!~ T|6z#K i0high = len(arr) - 1

3|f)Rw)~|0

Z UrU3dK"TX0f0while(low<=high):Python学习W TOr0`&g t&h"h{1Rx

!z#y8p~7X OA0print low,highPython学习j0w|&g"Fi

Python学习 J{ y5{$KZ

mid = (low + high)/2Python学习V9Vy5v{,w]y_

Python学习m |^,UQm)_'v

print mid

pt7X6pv9? cr0

;?@%Fd!MNx AC0if(arr[mid]==find):Python学习9\Ni8y{G

p CF#T Vd,f)uR/t0print "find %s index is %s",(find,mid)Python学习p-c9kv| q(A| L

Python学习;lP'BTM"T!z sK`

return

$a*v{-Z!X:Ts#~ fbz0 Python学习z9s_%q9~}[s

else:

*?.s{#K W-M e0

/`,e0Kk$v q#c0if(find > arr[mid]):Python学习8b FtU[U|k

.mGt$T&Sz0low = mid + 1

} f8|2d n[0

A%k-[p*bBSB0else:

4a+~^x F0 Python学习-t)cub W0EJ'V y'ZYY(T

high = mid - 1Python学习L"zp'O ]NU

Python学习 |kKFr8V&m5zg |S X

print "Not Find"

3{A0Y$n#c^0 Python学习T/r DBS3g}

return NonePython学习i3H,QO eA {/YKFp

Python学习AF:~ Bb{ZD g ^*r

#运行脚本Python学习 I'Bv ?][7?0^?)XM

Python学习4s nkY5eN7_o'p

if __name__ =="__main__":

6]YmMG0 Python学习M5H5ZL(u @Idps

halfSearch()

X$Y ~h:q3A0
顶:30 踩:34
对本文中的事件或人物打分:
当前平均分:-0.15 (197次打分)
对本篇资讯内容的质量打分:
当前平均分:-0.4 (184次打分)
【已经有168人表态】
28票
感动
24票
路过
14票
高兴
20票
难过
14票
搞笑
19票
愤怒
22票
无聊
27票
同情
上一篇 下一篇