鱼C论坛

 找回密码
 立即注册
查看: 946|回复: 7

[见证历程] [Python算法学习Day1] 1.2二分查找

[复制链接]
发表于 2022-9-29 14:50:02 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

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

x
本帖最后由 yanghongchen666 于 2022-9-29 14:51 编辑

二分查找(特点):
      1.有序的元素列表
        2.如果改元素包含在该列表,返回其元素位置; 否则返回null
        3.对于n个元素的列表使用二分查找只需要log_2 n 步

            举例:
                如果有32个元素的列表查找最后一个元素
                普通方法: 32次
                二分算法: log_2 32 = 5 (2^5=32) 5步




  1. #binary seacher
  2. def binary_search(list,item):
  3.     #low和high用于跟踪要在其中查找的列表部分
  4.     low = 0 #列表起点
  5.     high = len(list) -1 #列表终点(因为列表长度会比元素多一个所以这里要减一)

  6.     while low <= high:     #只要范围没有缩小到1一直循环
  7.         #每次检查中间元素
  8.         mid = int((low + high) / 2)  #如果(mid+high)不是偶数, 如果遇到切片为小数的情况使用int()强制转换为整形
  9.         guess = list[mid]

  10.         #找到元素
  11.         if guess > item:
  12.             high = mid-1

  13.         #如果猜小了 low的值往上增加
  14.         elif guess < item:
  15.             low = mid+1
  16.         
  17.         #如果猜大了 high的值往下减去
  18.         else:
  19.             return mid

  20.     return None #没有指定元素
复制代码



课后问题:

    1.1 假设有一个包含128个名字的有序列表,你要使用二分查找在其中
    查找一个名字,请 问最多需要几步才能找到?

   

    1.2 上面列表的长度翻倍后,最多需要几步?
        log_2  256 = 8 一共需要8步才能找到一个列表包含128个元素其中之一的元素


   1.3 一个列表为[-1,0,3,5,9,12]这样的数组使用二分查找找到9这个数字的位置
       
游客,如果您要查看本帖隐藏内容请回复
]1.3 请从数组[-1,0,3,5,9,12]中使用二分查找算法找到9这个元素的位置
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2022-9-29 14:52:20 | 显示全部楼层
太困了明天在补充点东西
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-29 15:11:08 | 显示全部楼层

回帖奖励 +10 鱼币

学到了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-30 13:27:52 | 显示全部楼层

回帖奖励 +10 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-9-30 14:42:37 | 显示全部楼层

回帖奖励 +10 鱼币

感谢分享!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-30 15:02:03 | 显示全部楼层

回帖奖励 +10 鱼币

感谢分享!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-30 16:42:12 | 显示全部楼层

回帖奖励 +10 鱼币

感谢分享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-10-19 14:50:04 | 显示全部楼层
感谢分享,学习中
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 08:29

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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