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

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

热度611票  浏览76次 时间:2011年7月19日 10:15
Python学习(U H'}(?{0_ s|&j

# -*- coding:utf8 -*-Python学习v AU(vx

io5Vvp Q0import osPython学习(QN#f?e^h"aD!Z

S6Z^9A'B{\ Z0import sysPython学习 h#vX1qs~k1I

g,sA&GWp{*fz:T0import mathPython学习!PT$e&W+W#jY

Python学习'C7tC5WD|

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

|/r#k@ Yw!Y0 Python学习S*DI4IH J7\S

'''''

];Fp(`i!o-i0 Python学习/r2X {6J@`:i

折半查找,2分查找

lb4i3S(^D_&KU0

]#_k3h{[p0折半查找的前提是数据是有序的

Cc| S [7v$E,R}7N0

mp h!X9PH0算法:mid = Math.floor(low+hight/2)Python学习Xk0p.RS'{H|

T9|@,cI/A:\ `4~0'''Python学习4he#\.Q$~ d:N Y-o-X

Python学习z'R~L;c0z:|!G_v N

mid = 0

lvwW)KoDs0

OhCc O3h3d'Ck-H0low = 0

^,J+N2Bt{L0 Python学习/Z V+y`4p&fy

high = len(arr) - 1

!mi(_t*x6^pk0 Python学习 lTea7I0w H"h#t

while(low<=high):Python学习*| U4X?3Dco7P

Python学习#r7h.s uUP)V,rY

print low,high

w9q4];edS R0

6o}.Dvf_0mid = (low + high)/2

1s8t8J1WA:Z3I0

| v)g#_W;C'Q PZN0print mid

!FnwO+}0 Python学习v(i7hsq`[oA'_

if(arr[mid]==find):Python学习)_1WHb:HXH%g"~.n

Python学习VV _UkV*Wsmm7V

print "find %s index is %s",(find,mid)Python学习)uQ1c BP

K^W;n+I;xo@R0return

ko"};\]BR0 Python学习)~9W.jR~)_K'X

else:Python学习F"A4tH$t5f6Pi(}-Y(s

Python学习p:_-M.zEl,X

if(find > arr[mid]):Python学习5lX8V'q#R4M3Q

Python学习5\}1J.t)B$y(}

low = mid + 1Python学习2N7L_|i{^C,Y

Python学习{~fHw

else:

Z2TIZ/\0 Python学习!};I.FJ H:B

high = mid - 1Python学习rG3o(gUh`

P7BR6C/@0v0print "Not Find"Python学习*_!l L ]&uk

;i Q b5~o'|/P0return None

;tN8~+D's1im ck0 Python学习9p6_!L}(\Z o6kQ

#运行脚本Python学习/W rD\@3a

Python学习_ K tT*?'u

if __name__ =="__main__":

'fF.MS9^0v {\"g.A0 Python学习Y*ibIh

halfSearch()Python学习g6w QEo

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