|
|
马上注册,结交更多好友,享用更多功能,让你轻松玩转新大榭论坛!
您需要 登录 才可以下载或查看,没有账号?注册
x
二分搜索 是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
3 {6 M( g/ f2 X* h
" j$ z: V6 @, W3 ], `- """
! h0 U: m) U! a4 u& ` - 顺序查找经典案例17 O6 ]4 W9 |; @( ~) T( w
- 素材来自新大榭Python学习社区,帖子号:7124#
% [1 v2 j$ M# |% c - 首页 http://www.daxie.net.cn/py/ - `9 \7 j/ n7 @- a3 ^# e* o9 c: |
- """
3 n& i6 h) e: g- Q - a=[1,3,4,6,7,8,10,13,14] #待查找的数组a,升序排列
6 L4 f: w; S3 B( J& h. M - key=int(input("要查找的数据为:")) #输入待查的目标数据key; C( k* M5 j6 b4 H7 Q0 S
- L=0 #最开始的比较范围从a[0]开始,故设定左边界下标为0
7 ]6 y& n. i# u+ r; [& j( O - R=len(a)-1 #最开始的比较范围到a[len(a)-1]结束,故右边界下标为len(a)-1
1 J6 p$ {2 B& l. o" T0 A - flag=False #初始化定义没有找到时的值为False
d, [4 G! z5 c6 ~+ P - while L<=R: #左边界小于有边界,即当范围内有数据时
6 V. ?6 Q; O/ V- S. ^( W! w! L - m=(L+R)//2 #取中间元素的下标m
3 h. X" ~5 {4 a1 H - if a[m]==key: #比较中间元素与key,若相等
5 R8 y: V& L# e l1 M* l9 _ - flag=True #满足相等条件,即成功找到元素
+ Y# H/ Q0 l7 T8 w+ @- P& W - break #结束循环,退出循环
9 \2 y2 h0 `: R) \# w; o* d - if key<a[m]: #如果key比中间元素a[m]小0 X# T: [+ i* M) k* _" n9 R( ]
- R=m-1 #右边界改为m左边一位的元素(m已经被比较不用划入范围)
5 M- Y7 R% k* G5 U1 @9 H0 E - else: #否则(key比中间元素大)& ~! `$ ^# [ G
- L=m+1 #左边界改为m右边一位的元素
7 C0 S( R' X3 Y - if flag==True:
; X$ s+ J- W3 a. Z* h/ {- C - print("key=",key,"在序列a[",m,"]中,","查找成功!") #成功查找的状态,输出查找成功
! G1 R( }" g( V9 [+ C - else:; D( Q4 m$ f$ n) @
- print("查找失败") #未找到的状态,输出查找失败2 \7 Z X. G/ z. a8 k$ ^2 x
- ) P( L( ^* w2 b( X* {# P. m; L, {
- #【分析思考】4 N2 t6 c7 d& b* [4 v# Q9 v- u( ^6 P
- # 略。。。
! h7 X- n9 S9 L/ H0 ], N" T6 {
" S' G. d/ I' e) j( c, a" `$ J6 S- """# u5 W! ^' x# W' s3 E1 z
- 注:选择性必修1配套资料《辅助衔接手册》P29 范例4
1 J) j" B7 ~0 s - """
复制代码
% D+ S1 N: O' y$ r3 X/ f实例2 : 递归
1 O3 D8 p8 H( E- # 返回 x 在 arr 中的索引,如果不存在返回 -1
: ]: B/ n. P; S% L; I# @ - def binarySearch (arr, l, r, x):
) Y/ V% w4 Q( @: O: d6 s8 U - + }( ^/ K" J9 o4 z f: a! {
- # 基本判断
9 S" y4 z4 s6 E5 R; E% ` - if r >= l: , j+ B8 o4 D7 p2 w
-
( \) D2 f: |8 V. ~8 G+ k - mid = int(l + (r - l)/2)
! Y( z! V2 @+ `5 }% W9 @ - # o: E0 I* V+ ~* U0 i
- # 元素整好的中间位置6 g4 q$ B" k) ?1 X4 Y. P1 ^
- if arr[mid] == x:
0 I% a' P" k0 F - return mid
( c5 I1 [8 H( ~; @. `' Y5 l - : s: d( [/ Y, }
- # 元素小于中间位置的元素,只需要再比较左边的元素& g5 S( Z: h. _$ R0 v
- elif arr[mid] > x: % C! Z8 }" d1 ]8 Y* L0 u' i1 @
- return binarySearch(arr, l, mid-1, x)
- [. w- T8 T( h$ N8 s5 U( Q* q/ { -
& u. u) F9 g( \) h( Q! c% t - # 元素大于中间位置的元素,只需要再比较右边的元素
! f/ U/ M: D' f1 G8 M - else:
2 Z' ^% Z1 y) X( }/ \ - return binarySearch(arr, mid+1, r, x) & F3 }) H# d* h# Y
- ( h u i1 [1 a% z5 S
- else: ( i) }/ F/ D2 h! P% I& m2 m/ R8 K
- # 不存在8 d, l. o2 ~& n) J
- return -16 X2 c, R7 H" P0 u, I. W6 J
-
7 t* M& G$ ~. z4 B - # 测试数组
) u9 ^8 }% X( g m7 S - arr = [ 2, 3, 4, 10, 40 ]
( X" N- k; r& E6 x5 L - x = 10 Q v2 P4 D% d
- 8 f) o) q$ o4 m/ o0 `
- # 函数调用
7 h. [5 N2 [$ q4 e6 d6 r% `( ^ - result = binarySearch(arr, 0, len(arr)-1, x) 3 s. _. v# Y/ {
-
9 Q' @" C: G7 w9 }5 h8 u1 L7 i - if result != -1:
* G. B! B8 { R( T - print ("元素在数组中的索引为 %d" % result )
- A* L" ~) U5 k. ^+ {; s - else: 2 H ~2 M/ ^ d4 H e9 D
- print ("元素不在数组中")
复制代码 执行以上代码输出结果为:
$ H, E4 O9 u$ u. r! f/ |4 u: U, E( @
: V; j' a. z, N! ~6 k( D: y) \7 u4 Z: ~% X2 a6 D( A) f# E

5 ~8 N, D, R; a# [0 f6 @
- t a4 x' O) P1 e9 ~. m' Z注:log2X+1 = ? 次 (X为序列的总元素数量) |
|