上一次，给大家分享了我自创的查找算法()

今天，给大家详细说说我自创的算法。

我们来看看二分查找的动图:

每次将待查找的区域减少大约1/2

二分查找的思路是对于有序列表，通过中间值的大小判断查找值的位置，每次将待查找的区域减少大约1/2,代码:

def binary_search(lst,val):    left=0    right=len(lst)-1    count=0    while left<=right:        mid=(left+right)//2        if lst[mid]==val:                        return [mid,count]        elif lst[mid]>val:            right=mid-1                    else:            left=mid+1        count+=1                    else:        return None

count是运行次数，用来比较O(logk n)的运行次数

那我们可以想想，能不能让每次将待查找的区域减少更多呢?

这就是我实现这个算法的原因。

我发现，如果能计算出“mid1”和“mid2”将列表分为3份呢?

所以,我可以计算mid1和mid2两个值:

相当于我将二分查找2次做的是合并为一次，那效率应该增加了吧！？(个人觉得无问题，如发现问题，欢迎评论!)

接下来，我将mid1和mid2各比较就行了（O(logk n) k=3 ):

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

我们比较count,当O(log2 n)的n=3^10时，count返回15,O(log3 n)，count返回8

计算次数减半了!

测试全代码:

from cal_time import *import time@cal_timedef twomidsearch(lst,val):	left=0	right=len(lst)-1	count=0	while left<=right:		mid=(left+right)//2		mid1=(left+mid)//2		mid2=(right+mid)//2		if lst[mid1]==val:			return [mid1,count]		if lst[mid2]==val:			return [mid2,count]		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					count+=1  	else:		return False		@cal_timedef binary_search(lst,val):    left=0    right=len(lst)-1    count=0    while left<=right:      #候选区有值        mid=(left+right)//2        if lst[mid]==val:                        return [mid,count]        elif lst[mid]>val:            right=mid-1                    else:            left=mid+1        count+=1                    else:        return None	        						max_n=3**15lst=list(range(1,max_n+1))for i in range(15):		t=twomidsearch(lst,max_n)	b=binary_search(lst,max_n)	print(t[1])	print(b[1])

结果:

twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0.0010001659393310546875 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0.0020000934600830078125 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0.00100040435791015625 seconds1223twomidsearch run time:0.0030000209808349609375 secondsbinary_search run time:0.0040004253387451171875 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0.0010001659393310546875 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0.000999927520751953125 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223twomidsearch run time:0.000999927520751953125 secondsbinary_search run time:0 seconds1223twomidsearch run time:0 secondsbinary_search run time:0 seconds1223

可见,我的算法速度还是很快的。[偷笑][狗头]

增加mid的个数,O(logk n)的k会更大,速度会更快。

今天就给大家讲到这里[谢谢]

发现问题欢迎评论!