yanghongchen666 发表于 2022-9-29 14:50:02

[Python算法学习Day1] 1.2二分查找

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

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

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



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

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

      #找到元素
      if guess > item:
            high = mid-1

      #如果猜小了 low的值往上增加
      elif guess < item:
            low = mid+1
      
      #如果猜大了 high的值往下减去
      else:
            return mid

    return None #没有指定元素


课后问题:

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

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

   1.3 一个列表为[-1,0,3,5,9,12]这样的数组使用二分查找找到9这个数字的位置
       
**** Hidden Message *****]1.3 请从数组[-1,0,3,5,9,12]中使用二分查找算法找到9这个元素的位置

yanghongchen666 发表于 2022-9-29 14:52:20

太困了明天在补充点东西{:10_266:}

okkboss 发表于 2022-9-29 15:11:08

学到了{:10_257:}

风一样的僧 发表于 2022-9-30 13:27:52

{:10_254:}

hornwong 发表于 2022-9-30 14:42:37

感谢分享！

1molHF 发表于 2022-9-30 15:02:03

感谢分享！

2388527437 发表于 2022-9-30 16:42:12

感谢分享

cqu20104225 发表于 2022-10-19 14:50:04

感谢分享，学习中
页: [1]
查看完整版本: [Python算法学习Day1] 1.2二分查找