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

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

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

8m2nc\gI*f0# -*- coding:utf8 -*-

} c3[&E@ d)U0

SV:O X;SQ6HB6]yW0import os

)cD*x Z4W,H'__0

u6N'X"QV#Z0import sys

lW J$BeC s C0

B"o\2l]!VM0import math

1ws)v_c:pml1c'Z0c5l0 Python学习K'UA1x6VO/SaX

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

Hk{MAI0 Python学习 \"[RX!eUf

'''''Python学习~ e+["`$X6H

Python学习!K)Al D/I.A8n

折半查找,2分查找

#Z2G#n'E0nHu'BQ0 Python学习n ~HZ4N!uH

折半查找的前提是数据是有序的

n9t8RR%l0

*SgA,oz,}1Vn0算法:mid = Math.floor(low+hight/2)

O8L r n;k5Fc~0 Python学习&W NK0w!_,md

'''

aox'd~ f0

B']$~ TJ7n0mid = 0

ZaJ5zR6i xh0

%Q N!V4@7d` T]N3k0low = 0

V'P-N7~v-@?9x0

-},BSi(R0high = len(arr) - 1

m0DO8|;?n g,y0 Python学习8hBs8z^ ?e@

while(low<=high):

px \@8{gp0 Python学习.`%@0U"z\*H COo

print low,highPython学习$H Hk(p9@-B

Python学习.v,u-E&D.QCB8~

mid = (low + high)/2Python学习$n+DA9VEGM Y.Z7\]

BNGt}6v!G]0print midPython学习oC~_Ve+K

Python学习g i}7C)n*h%f6r

if(arr[mid]==find):Python学习O I?O {r9m)D

Python学习/[#l)|+g~;uH;P

print "find %s index is %s",(find,mid)Python学习sb6ZOsy{

AI m1P&G@'Dh0return

!c8k w_-q0

#\ TR!OQ5[g'By0else:

#q:?*\,|}/xp a8T0 Python学习U B1B Ei"F:\Q P

if(find > arr[mid]):Python学习g3\er0E(x2|

Python学习 RZ4|f K*R3uy

low = mid + 1

_2qsX XB X:e5^0 Python学习~1{7xd^-K(CL

else:

1nW'aUG6~0W0 Python学习$?Le-A2]`

high = mid - 1Python学习Ey$L/\ Vu4{

Vz8ha$@0print "Not Find"Python学习 R5a8K W;Ep

Python学习?e(SK!Rq+U g

return None

!XI'nHC u0 Python学习 b6E1Xpqg.`.m

#运行脚本

_G#lg+S?&V0 Python学习^v%`E`U&v3hh,\

if __name__ =="__main__":Python学习.A2h9^OLS \?ip

Python学习/Eos(c8s(M

halfSearch()Python学习E5n)a#?"ov

顶:34 踩:37
对本文中的事件或人物打分:
当前平均分:-0.15 (230次打分)
对本篇资讯内容的质量打分:
当前平均分:-0.49 (208次打分)
【已经有183人表态】
32票
感动
26票
路过
15票
高兴
21票
难过
16票
搞笑
20票
愤怒
24票
无聊
29票
同情
上一篇 下一篇