说起查找算法,常见的就线性查找和二分查找两种

线性查找:

二分查找:

[憨笑]关于查找算法我的讲解:

线性查找的时间复杂度:O(n)

二分查找的时间复杂度:O(log2 n)

我改进的二分查找时间复杂度:O(logk n)

我默认k=3

这差距就太大了！[惊呆]

这么说吧,如果n=2^32,二分查找:计算32次

用时:计算机每秒执行10^7次基本操作,时间:32/10^7=3.2e-06秒

线性查找,n=2^32,计算次数:2^32

2^32 和 32 得差多少啊！！！

用时:2^32约等于42亿,4.2^(10^9)/10^7=4200秒

二分查找，永远的“神”!

但在O(logk n)面前还是小巫见大巫:

k=3

n=3^3^3=7625597484987

而二分查找的n约等于42亿

但3^3^3远远大于2^32

但O(log3 n)的计算量呢?

log3 3^3^3=3^3=27次

what!?[给力]

在n差距那么大的情况下，O(log3 n)的计算量竟然比O(log2 n)还少！

我的算法,永远的神!

原因是:

我的算法每次将查找区域减少2/3,而二分查找每次减少1/2

代码上:

def twomidsearch(lst,val):	left=0	right=len(lst)-1		while left<=right:		mid=(left+right)//2		mid1=(left+mid)//2		mid2=(right+mid)//2		if lst[mid1]==val:			return mid1		if lst[mid2]==val:			return mid2		if lst[mid1]>val:			right=mid1-1								if lst[mid2]>val:			right=mid2-1					if lst[mid1]<val:			left=mid1+1					if lst[mid2]<val:			left=mid2+1					  	else:		return False

增加mid的个数O(logk n)中的k也会变化,越多效率越高

麻烦大家看看我的代码有没有问题[谢谢]

下次给大家讲讲思路[可爱]