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

yanghongchen666

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

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

1. 
   
2. #binary seacher
   
3. def binary_search(list,item):
   
4.     #low和high用于跟踪要在其中查找的列表部分
   
5.     low = 0 #列表起点
   
6.     high = len(list) -1 #列表终点(因为列表长度会比元素多一个所以这里要减一)
   
7. 
   
8.     while low <= high:     #只要范围没有缩小到1一直循环
   
9.         #每次检查中间元素
   
10.         mid = int((low + high) / 2)  #如果(mid+high)不是偶数, 如果遇到切片为小数的情况使用int()强制转换为整形
    
11.         guess = list[mid]
    
12. 
    
13.         #找到元素
    
14.         if guess > item:
    
15.             high = mid-1
    
16. 
    
17.         #如果猜小了 low的值往上增加
    
18.         elif guess < item:
    
19.             low = mid+1
    
20.         
    
21.         #如果猜大了 high的值往下减去
    
22.         else:
    
23.             return mid
    
24. 
    
25.     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这个元素的位置

yanghongchen666

太困了明天在补充点东西

okkboss

学到了

风一样的僧

hornwong

感谢分享！

1molHF

感谢分享！

2388527437

感谢分享

cqu20104225

感谢分享，学习中