二分查找:又称折半查找,输入一个有序的元素列表(必须是有序的),将列表中间位置记录的元素与查找元素比较,如果查找的元素包含在列表中,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的元素大于查找元素,则进一步查找前一子表,否则进一步查找后一子表,重复以上过程,直到找到满足条件的记录,使查找成功,二分查找返回其位置;或直到子表不存在为止,此时查找不成功,返回None。 二分查找算法要求:。必须是有序列表; 二分查找算法时间复杂度:O(logn) 二分查找算法优点:比较的次数少,查找速度快,平均性能好,占用系统内存较少。 defbinarysearch(list,item): low0 highlen(list)1 whilelowhigh: midint((lowhigh)2)整除计算也可用mid(lowhigh)2 guesslist〔mid〕 ifguessitem: returnmid ifguessitem: lowmid1 else: highmid1 returnNone mylist〔1,3,5,6,8,7,9,12,18,45〕 print(binarysearch(mylist,2)) print(binarysearch(mylist,12))