python算法与数据结构-二分查找算法
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。
因此折半查找方法适用于不经常变动而查找频繁的有序列表。
递归实现二分查找,代码如下所示:
# coding=utf-8 #二分查找,递归算法 def binary_search(alist,item): n = len(alist) if n>0: mid = n//2 if(alist[mid] == item): return True elif item < alist[mid]: return binary_search(alist[:mid],item) else: #这里需要是mid+1,因为mid是中间值上面已经判断了 return binary_search(alist[mid+1:],item) return False if __name__ == "__main__": li = [17, 20, 26, 31, 44, 54, 55, 77, 93] print(li) res = binary_search(li,26) print(res) res2 = binary_search(li,88) print(res2) """ [17, 20, 26, 31, 44, 54, 55, 77, 93] True False """
非递归实现二分查找,代码如下所示:
# coding=utf-8 #二分查找,非递归算法 def binary_search(alist,item): """二分查找,非递归""" n = len(alist) first = 0 last = n-1 while first <= last: mid = (first+last)//2 if(alist[mid] == item): return True elif item < alist[mid]: # 这里为什么是last,因为要找的值比中间的值小,列表又是有序的,所以只需要找列表的前面一部分就行,所以last = mid - 1 last = mid-1 else: # 这里为什么是first,因为要找的值比中间的值大,列表又是有序的,所以只需要找列表的后面一部分就行,所以first = mid+1 first = mid+1 return False if __name__ == "__main__": li = [17, 20, 26, 31, 44, 54, 55, 77, 93] print(li) res = binary_search(li,26) print(res) res2 = binary_search(li,88) print(res2) res3 = binary_search(li, 77) print(res3) """ [17, 20, 26, 31, 44, 54, 55, 77, 93] True False True """
上面的最坏时间复杂度:O(logn),二分查找又叫折半查找,每次查找都是以2为底取对数,所以最坏时间复杂度:O(logn)。