|
|
马上注册,结交更多好友,享用更多功能,让你轻松玩转新大榭论坛!
您需要 登录 才可以下载或查看,没有账号?注册
x
二分搜索 是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
3 B6 n1 u5 d3 g- c2 f0 E1 [
A' D) Y; S& I- """- B* |3 q0 X( r3 u
- 顺序查找经典案例17 f Y: [7 U# @! W
- 素材来自新大榭Python学习社区,帖子号:7124#
8 a' h5 O1 `1 |3 Q5 Y - 首页 http://www.daxie.net.cn/py/
" G+ ^3 }/ ^8 q - """
- S l) H) L1 o4 T+ b/ j9 q - a=[1,3,4,6,7,8,10,13,14] #待查找的数组a,升序排列1 k4 L- y: c& B# B5 Q- @
- key=int(input("要查找的数据为:")) #输入待查的目标数据key- {) C( l' U6 V& S: a
- L=0 #最开始的比较范围从a[0]开始,故设定左边界下标为0
' ~- \1 J- o/ T' h0 p" I1 } - R=len(a)-1 #最开始的比较范围到a[len(a)-1]结束,故右边界下标为len(a)-1
, E6 ?/ K, a- {6 J - flag=False #初始化定义没有找到时的值为False% M& c! ]" d5 s
- while L<=R: #左边界小于有边界,即当范围内有数据时, @ F: R0 o1 C" S
- m=(L+R)//2 #取中间元素的下标m) K1 M3 h& j0 G; E0 T. @
- if a[m]==key: #比较中间元素与key,若相等
, t" U4 c4 _1 d8 P1 G+ T - flag=True #满足相等条件,即成功找到元素! _% i; c2 `6 }- F# Y$ D
- break #结束循环,退出循环 s" @) e9 {# M/ H" x1 Q1 m% |
- if key<a[m]: #如果key比中间元素a[m]小* o9 A7 d4 n; W6 n2 Q8 p. d
- R=m-1 #右边界改为m左边一位的元素(m已经被比较不用划入范围)
; T3 Y3 e) C/ c d3 t# E# K - else: #否则(key比中间元素大)5 r/ I/ y# j' ` z5 ]' }
- L=m+1 #左边界改为m右边一位的元素
: r% [8 h i9 D7 U - if flag==True:
9 n" ^! T0 y0 H7 x" m) h7 d: T' u - print("key=",key,"在序列a[",m,"]中,","查找成功!") #成功查找的状态,输出查找成功
0 @4 a- \# ?: B+ }. F- x - else:
! S9 d. L0 C0 ~( L) U - print("查找失败") #未找到的状态,输出查找失败
; H- Z/ i, `3 s8 B
: m8 U$ Q. y c- #【分析思考】
7 q* q5 z9 k3 p! u: l9 C - # 略。。。, b0 D& \4 p* [, M8 F
4 N' y" h9 C, R9 t+ I$ o; j- """& U5 i! E( t% f8 w
- 注:选择性必修1配套资料《辅助衔接手册》P29 范例4$ i% j. O2 j# j5 x
- """
复制代码
2 _1 [: r7 P+ [$ X. z实例2 : 递归
/ r0 @: a# U; @( ]1 w+ g- # 返回 x 在 arr 中的索引,如果不存在返回 -11 }5 U, x2 L. [
- def binarySearch (arr, l, r, x):
0 {& _- t3 }. _ -
4 i! V( B4 w& x - # 基本判断
2 b! e7 e# f- J - if r >= l: / J) w* j$ Z& Y+ n) d+ X
-
3 V& D. F' i( h( r - mid = int(l + (r - l)/2)+ f, l9 a! g- s6 G6 P9 ~
-
. y9 u* |* u( G$ x# B$ i' q, I - # 元素整好的中间位置# T2 g+ E' ~3 z
- if arr[mid] == x:
$ Q+ O# o$ n8 a" {: E+ p4 @* s - return mid 2 T1 B" ]( V4 p+ x
- + [5 f7 O, A2 p
- # 元素小于中间位置的元素,只需要再比较左边的元素
+ Q5 S4 S7 z/ b. _ N - elif arr[mid] > x:
% ?- p+ A a! c - return binarySearch(arr, l, mid-1, x)
8 P6 f7 s9 A0 W+ ~9 w* j -
% P1 n' L4 j- H5 ^$ c% ]) I- R, a - # 元素大于中间位置的元素,只需要再比较右边的元素8 s1 Z8 @2 y: i- p. g( |( p
- else: $ x8 y( f. i1 e, R8 A
- return binarySearch(arr, mid+1, r, x)
( S( x7 L, L- x- l5 H- b" e) n -
2 g" e6 @& v' K' e- V8 X, \# d - else:
3 ~" V; F0 x \/ k4 K& F' N6 w - # 不存在* C# u, H2 z* ^! B% w, O/ D" y) p( h
- return -1
1 C0 ?* G- o/ O+ g) P1 _- w$ k -
, g! X F! I. X8 l7 }/ [. l - # 测试数组
# W5 h' T" y: W. K3 `" v - arr = [ 2, 3, 4, 10, 40 ]
7 a# l+ q/ f- R6 S# J - x = 107 O5 R1 V! J, N: c8 H- M" U
- ' k4 R4 [6 l$ Z
- # 函数调用9 h; T7 Q8 V' S, f! s m
- result = binarySearch(arr, 0, len(arr)-1, x) , C/ D- w- ?' H, `/ z# {% I4 A0 t* K
- $ R: b( R9 q; G- Q
- if result != -1:
' v( W9 k2 P4 {) ~/ @$ o0 x - print ("元素在数组中的索引为 %d" % result )9 z% I# x7 f" x- n! ]0 [
- else:
3 F# ?" V. p, o7 ?+ r - print ("元素不在数组中")
复制代码 执行以上代码输出结果为:, M' H. X5 }8 x9 e( T
. G4 r; X- {! w: s' I
+ b M8 ^6 x9 u) q% S2 _
! C' f" Y3 v; G& R: ^" R% g) r 9 G2 L ]' s$ N
& ]7 p7 x& Q8 r5 f# @2 P# @注:log2X+1 = ? 次 (X为序列的总元素数量) |
|