简介二分查找算法与相关的Python实现示例
二分查找BinarySearch的思想:
以有序表表示静态查找表时,查找函数可以用二分查找来实现。
二分查找(BinarySearch)的查找过程是:先确定待查记录所在的区间,然后逐步缩小区间直到找到或找不到该记录为止。
1二分查找的时间复杂度是O(log(n)),最坏情况下的时间复杂度是O(n)。
假设low指向区间下界,high指向区间上界,mid指向区间的中间位置,则mid =(low+high)/2;
具体过程:
1.先将关键字与mid指向的元素比较,如果相等则返回mid。
2.关键字小于mid指向的元素关键字,则在[low, mid-1]区间中继续进行二分查找。
3.关键字大于mid指向的元素关键字,则在[mid+1,high]区间中继续进行二分查找。
用Python实现二分查找示例:
>>>deffind(self,num): l=len(self) first=0 end=l-1 mid=0 ifl==0: self.insert(0,num) returnFalse whilefirst<end: mid=(first+end)/2 ifnum>self[mid]: first=mid+1 elifnum<self[mid]: end=mid-1 else: break iffirst==end: ifself[first]>num: self.insert(first,num) returnFalse elifself[first]<num: self.insert(first+1,num) returnFalse else: returnTrue eliffirst>end: self.insert(first,num) returnFalse else: returnTrue >>>list_d=['a','b','c','d','e','f','d','t'] >>>value_d='t' >>>aa=find(list_d,value_d) >>>aa True >>>value_d='ha' >>>aa=find(list_d,value_d) >>>aa False