Python查找算法之我的算法VS二分查找，真正的差之毫厘谬以千里

今天，我们来看看直观地看看我自创算法VS二分查找 的时间、计算量大比拼吧！

二分查找，时间复杂度为O(log2 n)

我的算法，时间复杂度可能为O(logk n)

大家应该知道时间复杂度的效率吧？(不知道？学一学:算法的时间复杂度)

log是对数，logk n的得数r满足k^r=n

所以，log中k越大，得数越小

这么说，k如果大于2，那我的算法效率应该比二分查找高吧(我的算法默认k=3)

除了数学计算，我们用@cal_time的方法计算时间

(不知道？看看:时间计算器)

代码:

from cal_time import *
import time

@cal_time
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		

@cal_time
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	
        						
@cal_time 
def all_test(max_n):
	lst=list(range(1,max_n+1))
	
	for i in range(25):
		t=twomidsearch(lst,max_n)
		b=binary_search(lst,max_n)
		print(t[1])
		print(b[1])
	
max_n=550000000
all_test(max_n)	

(电脑性能低的将max_n调小！目前5.5亿，有可能死机！)

运行结果令我大吃一惊：

twomidsearch run time:0.0012992382049560546875 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0.0099947452545166015625 seconds
15
29
twomidsearch run time:0.0009992122650146484375 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0.003997802734375 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0.0019989013671875 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
twomidsearch run time:0.0009992122650146484375 seconds
binary_search run time:0.0059967041015625 seconds
15
29
twomidsearch run time:0 seconds
binary_search run time:0 seconds
15
29
all_test run time:22.956223964691162109375 seconds

注意第93、94行！

这差距！……厉害厉害

5.5亿在计算量最大时，我的算法最少只用了0.0009992122650146484375秒！

所以，下一次在使用有序列表查找时，我觉得我的算法才厉害

今天就给大家讲到这里

大家觉得我的算法实用吗？欢迎评论！