+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-07(6)

2019-08(116)

2019-09(98)

2019-10(17)

2019-11(5)

python 二分查找的三种方式

发布于2020-09-13 21:27     阅读(559)     评论(0)     点赞(10)     收藏(4)


0

1

2

3

4

⼆分查找. 每次能够排除掉一半的数据. 查找的效率非常高. 但是局限性比较大. 必须是有序列才可以使用二分查找

要求: 查找的序列必须是有序序列.

三种方法:

1.纯算法

lst = [11, 22, 33, 44, 55, 66, 77, 88, 99, 123, 234, 345, 456, 567, 678, 789]
n = 567
left = 0
right = len(lst)-1
count = 1
while left <= right :
    middle = (left +right)  // 2
    if n > lst[middle] :
        left = middle + 1
    elif n < lst[middle] :
        right = middle -1
    else :
        print(count)
        print("存在")
        print(middle)
        break
    count += 1
else :
    print("不存在")

2.递归法

# lst = [11, 22, 33, 44, 55, 66, 77, 88, 99, 123, 234, 345, 456, 567, 678, 789]
def  binary_search(n,left,right):
    if left <= right :
        middle = (left+right) // 2
        if  n  <lst[middle] :
            right = middle -1
        elif n >lst[middle]:
            left = middle  + 1
        else :
            return middle
        return binary_search(n,left,right)  # 不加return返回永远是None
    else :
        return -1  #没有找到
 
 
print(binary_search(567,0,len(lst)-1)

3.另类方法

def biinary_search(ls,target):
    left = 0
    right = len(ls) - 1
     if left > right:
        print("不不在这⾥里里")
    middle = (left + right) // 2
    if target < ls[middle]:
        return binary_search(ls[:middle], target)
    elif target > ls[middle]:
        return binary_search(ls[middle+1:], target)
    else:
        print("在这⾥里里")
binary_search(lst, 567)

原文链接:https://www.cnblogs.com/python960410445/p/13633582.html

0

1

2

3

4

5

6

7

8

9



所属网站分类: 技术文章 > 博客

作者:python是我的菜

链接: https://www.pythonheidong.com/blog/article/519845/192217689d10f2631122/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

10 0
收藏该文
已收藏

评论内容:(最多支持255个字符)