二分查找

2019/05/03 15:15
阅读数 5

一:二分查找的递归实现:

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好。
缺点是要求待查表为有序表
因此,折半查找方法适用于不经常变动而查找频繁的有序列表。
二分查找的工作原理如下:
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功。
否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为

二分查找的前提是表示有序列表“

分析:

二分递归查找实现:

def my_search(alist,item):
    n=len(alist)
    # 递归结束条件
    if n>0:
        # 折半查找
        mid=n//2

        if alist[mid]==item:
            return True

        elif item < alist[mid]:
            # 继续递归查找
            return my_search(alist[:mid],item)

        else:
            return my_search(alist[mid+1],item)

    return False

if __name__=="__main__":
    li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
    print(my_search(li,20))

二:二分查找的非递归实现

代码实现:

def my_search2(alist,item):
    n=len(alist)

    # 起始位置 ,0
    first=0
    # 结束位置
    last=n-1

    while first<=last:
        #折半
        mid=(first+last)//2
        # 判断中间的元素
        if alist[mid]==item:
            return True
        elif item<alist[mid]:
            last=mid-1

        else:
            first=mid+1
    return False


if __name__=='__main__':
    # 二分必须是有序的列表
    li=[17, 20, 26, 31, 44, 54, 55, 77, 93]
    print(my_search2(li,20))

 小知识点:

if __name__ == '__main__'的意思是:当.py文件被直接运行时,if __name__ == '__main__'之下的代码块将被运行;(相当于一个程序的入口)
当.py文件以模块形式被导入时,if __name__ == '__main__'之下的代码块不被运行。

 

展开阅读全文
def
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部