新大榭论坛

 找回密码
 注册

QQ登录

只需一步,快速开始

《新大榭》- 创大榭地方网络社区先锋品牌 新大榭始终专注于地方网络社区平台的建设 关于我们- [大记事]- 留言建议- [新手报道]

发布 .新大榭软件管家(Excel版) V6.0版 财务/仓库/生产/销售/采购/行政/人事/校园 .公告 - 客户 - 打赏 - 职场 - Excel - Python.

新大榭镜像-音乐-法律-图书-高中课堂-实验 广告是为了能更好的发展 [欢迎商家支持本站互利共赢] 广告位招租.首页黄金广告位等您来!联系 13566035181

查看: 1124|回复: 0

[笔记] 7124 - [选修1]Python 二分查找

[复制链接]
发表于 2021-2-18 09:39:32 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转新大榭论坛!

您需要 登录 才可以下载或查看,没有账号?注册

x
二分搜索 是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

3 q9 w% D# ^+ N" [% @ Binary_search_into_array.png ! K- ^( I1 ~1 b- ]9 h
  1. """
    ) ^) c: C7 [) Q5 J( x3 U" H* C
  2. 顺序查找经典案例1
    2 V8 D0 u. b) `! \: L% M, r
  3. 素材来自新大榭Python学习社区,帖子号:7124#2 a+ i  m$ T) ]; ]' y* x
  4. 首页 http://www.daxie.net.cn/py/
    6 n7 Z- {8 w( H1 l+ [$ a, i& O
  5. """0 W; `% N& k, w
  6. a=[1,3,4,6,7,8,10,13,14] #待查找的数组a,升序排列( p+ [" O$ p/ N! w/ H" T. }- P( X
  7. key=int(input("要查找的数据为:")) #输入待查的目标数据key
    # U1 N# ^3 n/ C( Q
  8. L=0 #最开始的比较范围从a[0]开始,故设定左边界下标为0
    0 c) b9 P: y) x6 j: W" C3 }
  9. R=len(a)-1 #最开始的比较范围到a[len(a)-1]结束,故右边界下标为len(a)-1- C# s/ V2 ?, H6 d4 h# P
  10. flag=False #初始化定义没有找到时的值为False
    5 x: q6 V2 P/ \
  11. while L<=R: #左边界小于有边界,即当范围内有数据时
    ( `1 S, a8 _9 }; D9 b' }' A. g8 o
  12.     m=(L+R)//2 #取中间元素的下标m5 L+ U! f  n" ]3 g& d4 D
  13.     if a[m]==key: #比较中间元素与key,若相等4 o( R( ~2 F6 ?' p7 w2 V1 s# p
  14.         flag=True #满足相等条件,即成功找到元素6 V  u+ l* f( f) U: j( l7 {2 w
  15.         break #结束循环,退出循环
    1 _' O7 C3 A0 V4 g" u$ r
  16.     if key<a[m]: #如果key比中间元素a[m]小
    8 F: r' g- T1 O+ d
  17.         R=m-1 #右边界改为m左边一位的元素(m已经被比较不用划入范围)8 w4 }) }$ E, [! b0 N& n% @
  18.     else: #否则(key比中间元素大)3 q: m# @, {/ Q( |# f5 b
  19.         L=m+1 #左边界改为m右边一位的元素" ?* Q0 d3 y. Z# A7 i
  20. if flag==True:
    9 N9 N, x! B$ G* E# m4 A
  21.     print("key=",key,"在序列a[",m,"]中,","查找成功!") #成功查找的状态,输出查找成功
    0 F3 @% R4 D) q
  22. else:: v- M3 o" k5 I, {/ V7 ^& T6 z5 @
  23.     print("查找失败") #未找到的状态,输出查找失败3 G% r0 M8 i. U" p9 s# b. E$ O1 s. J

  24. $ D( M! a% ]* ]- \5 e6 x# B7 T+ ~0 }
  25. #【分析思考】
    . F0 @8 G3 K8 e/ ^. `  h8 K' R. @
  26. # 略。。。) l$ R3 `! C6 `7 W

  27. 3 s4 l) G5 q' b7 V! |
  28. """/ \; s% b6 z% U3 j
  29. 注:选择性必修1配套资料《辅助衔接手册》P29 范例4, b  D& A0 Y/ f  Y0 x6 T' K' r$ G+ @
  30. """
复制代码

6 z# }( C' ^( O' O实例2 : 递归
5 U" k/ B6 u& l
  1. # 返回 x 在 arr 中的索引,如果不存在返回 -1& u  L8 K$ y+ H( X
  2. def binarySearch (arr, l, r, x):
    " U  G8 c  R+ ?. X9 z- E
  3.   
    6 }, C$ S1 b- r. t
  4.     # 基本判断' I' q; J" m( x& `& u; Q- O
  5.     if r >= l: # E6 k4 d) ~# \% e
  6.   
    - o; L) ?) `' m2 G
  7.         mid = int(l + (r - l)/2)2 c5 T, P1 R8 e- J- o+ m
  8.   
    2 O4 f  ~0 |# B% s1 i0 G, w/ M
  9.         # 元素整好的中间位置( u6 Y/ e9 [- a8 y9 q6 l3 n$ W
  10.         if arr[mid] == x:   O7 c/ o! E8 a! [2 ?/ d1 ?
  11.             return mid
    ) ^0 F+ E& f; \" W% l9 l
  12.             U) x- N4 p& a! [
  13.         # 元素小于中间位置的元素,只需要再比较左边的元素
    3 w9 Y- ^4 k9 u) W! j. _
  14.         elif arr[mid] > x: ) r5 F/ K4 M9 l  V- {
  15.             return binarySearch(arr, l, mid-1, x)
    ) _1 F1 W3 ~: x* D+ g1 k" A' ?
  16.   # p; U0 Y! M1 {# M3 j+ I
  17.         # 元素大于中间位置的元素,只需要再比较右边的元素
    * O+ j* E. s! F. O$ [5 x; `9 `
  18.         else:
    1 z( N1 h6 z) c' M* _$ E+ m) m% O
  19.             return binarySearch(arr, mid+1, r, x) 0 g! x( X. m% Z
  20.   ' l* x+ T$ E" b
  21.     else:
    0 R/ K1 O( E( j
  22.         # 不存在/ h# F. O0 C( z1 t- F. B
  23.         return -12 {" }4 b$ }7 U7 y6 k% e5 e+ ?
  24.   # {& k) U3 {8 E/ V. Y7 s( b; K) C
  25. # 测试数组
    * j' n% T4 d! Z! U3 _& x
  26. arr = [ 2, 3, 4, 10, 40 ]
    # X% Q; u! b- |. r/ x0 s
  27. x = 10
    . Y1 c/ u# F, |7 g5 Q  e8 V
  28.   % d3 C" O. q9 R
  29. # 函数调用
    & G% b/ r9 j2 `; y; o) r
  30. result = binarySearch(arr, 0, len(arr)-1, x) ) c( ?: h* }4 Y% M5 M2 M1 w
  31.   - K% Z- [2 M- i6 @% R, `5 Q
  32. if result != -1:
    3 I2 v1 @6 t2 ^
  33.     print ("元素在数组中的索引为 %d" % result ), V% W3 x# T; c% |0 P
  34. else:
    ' y" v+ k& ~8 q2 o; l
  35.     print ("元素不在数组中")
复制代码
执行以上代码输出结果为
( q9 z' [  R, l% J1 ^
  1. 元素在数组中的索引为 3
复制代码
6 O0 ?$ S: ^; W( W" B
& ]7 R" s) y6 w

# v  l/ Q# r8 Q; u& y7 C: }" M+ Z9 ]7 j  s2 X/ h
0 [3 {& l6 q; _
注:log2X+1 = ? 次 (X为序列的总元素数量)

7124-01-01.py

1.23 KB, 下载次数: 71, 下载积分: 财富 -1 点

新大榭Python学习社区培训、Excel业务指导、办公软件定制、网站建设;新大榭探索实验室欢迎您!http://lab.daxie.net.cn/
Q群推荐 大榭本地求职招聘QQ群,欢迎转发分享本地招聘信息资讯! 官方招聘1群(已满);官方招聘2群:315816937 *
您需要登录后才可以回帖 登录 | 注册

本版积分规则

文字版|小黑屋|新大榭 ( 浙ICP备16018253号-1 )|点击这里给站长发消息|

GMT+8, 2026-4-28 18:05 , Processed in 0.096245 second(s), 22 queries , Gzip On.

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表