pyton实现二分查找
搜索: 二分查找: 递归代码:def binary_search(alist,item): """二分查找""" low=0 n=len(alist) if n>0:#递归终止条件 mid=n//2 if item==alist[mid]: return True elif item<alist[mid]: return binary_search(alist[:mid],item) elif item>alist[mid]: return binary_search(alist[mid+1:],item) else: return False if __name__=="__main__": li=[17,20,26,31,44,54,55,77,93] print(binary_search(li,55)) print(binary_search(li,100))递归分析:
(1)对于二分查找,针对的是排序好的一个元素。
(2)每次需要进行比较中间元素与所要查找元素的大小
(3)如果要查询的元素比mid处的元素小,辣么就往左边部分继续进行二分查找,即alist[:mid]
(4)如果要查询的元素比mid处的元素大,辣么就往右边部分继续进行二分查找,即alist[mid+1:],继续递归下去
(5)终止条件为n<=0的情况。所以完整代码见上
def binary_search(alist,item): """非递归,二分查找""" frist=0 last=len(alist)-1 while frist<=last: mid=(frist+last)//2 if item==alist[mid]: return True elif item<alist[mid]: last=mid-1 else : frist=mid+1 return False if __name__=="__main__": li=[17,20,26,31,44,54,55,77,93] print(binary_search(li,55)) print(binary_search(li,100))非递归分析:
(1)首先我们还是和递归一样找到中间元素,也就是mid=(frist+last)//2,就是7.
(2)判断所要查找的元素与mid元素进行比较。
(3)比mid小,就需要更改last,使得last=mid-1
(4)如果所查元素比mid元素大,则需要更改frist使得frist=mid+1
(5)终止条件是frist<=last
最优复杂度:就是刚好所要查找的元素正好等于mid所指的值。