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

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

热度631票  浏览82次 时间:2011年7月19日 10:15

0C!ibs6`o0# -*- coding:utf8 -*-Python学习&x a7T3|?X(bn*Ap

Python学习V-]{ v `%y5G

import osPython学习p*`*BAo*mS

Python学习E)Oe:V yn5[

import sys

JL9zz ev0

%l-j%M$y`!\0import mathPython学习5D1mTt4DA+X]

Python学习#A6e XY%d QQ&O)a9Q

def halfSearch(arr=[1,2,3,4,5],find = 1):Python学习2\QT D,G2W.]7b

x}Gr[9[t0'''''

[W[3_$M$H5gR0 Python学习PcK8E^n

折半查找,2分查找

v8U]/QU6D c7Q0 Python学习a[ X1h&~.`6a3B[-ch

折半查找的前提是数据是有序的Python学习({AC8U+O3x%L7Dp

O-AA!L-VTU0算法:mid = Math.floor(low+hight/2)

KW@j?:u@8C0 Python学习 Y,\P!PCQX

'''Python学习 {yD e5B2@c g6`+N

Python学习v1K\w ^X5S

mid = 0Python学习[x5M*J'f C

y/k&_0c Tz'P6sY0low = 0Python学习5@R,]GAE!y5ml

Python学习rH&P?G_6M6Bkb

high = len(arr) - 1Python学习 oo[k-fm!y`

Python学习2If0v&Z5J)el/u

while(low<=high):

e5sVHdT,{OJj;jM0 Python学习jc(n+n K/w&Cf

print low,highPython学习5@jRd2gJ

Python学习)k cE,~_g#F%L%]e{

mid = (low + high)/2

0kw*Bz7n0

s }.d+v%Rp3T{0print midPython学习9H'AvkA/Yas.B;K

Python学习PpV:i.{!^u$X

if(arr[mid]==find):Python学习&Ko9Q0v*Ch

Python学习ZYcm+agB-b

print "find %s index is %s",(find,mid)

AC.E6?;C+V5gGE]0 Python学习.U:?7e4XF*j

return

/s j F^}}&Gv4U,~0 Python学习 xR}&Iy?j:a,F{'a!g

else:

i'K&T_3D h*} f0 Python学习$jAxCxDOk

if(find > arr[mid]):Python学习'O^d'S2N9h(`

J B{AA#pz7c'YC0low = mid + 1

E7C6XP }8?vD$O0 Python学习r6^,o!eezZi:k

else:Python学习2by.V8M)_)E5?S

Python学习iK"bZF5I7w

high = mid - 1

c}Ne,f$G8S"f~0

RQ&M,~q\0print "Not Find"Python学习&W'H6{"{/\5x$G

)h jCcb`.j*Et'`q0return None

(Oq!GR/h:R/j0 Python学习@i5tdO$~ ]W-}

#运行脚本

7M3h:k hrb-K0 Python学习(X1SV1J#k6M ^#Y

if __name__ =="__main__":Python学习"rq6pb-\5Z

/o#S5c)YZO0halfSearch()Python学习 V"@#|F\M

顶:31 踩:34
对本文中的事件或人物打分:
当前平均分:-0.17 (203次打分)
对本篇资讯内容的质量打分:
当前平均分:-0.39 (189次打分)
【已经有174人表态】
29票
感动
24票
路过
15票
高兴
20票
难过
15票
搞笑
20票
愤怒
23票
无聊
28票
同情
上一篇 下一篇