Bruteforce比二进制搜索花费更多的时间来查找排序列表的第一个元素

Question

我对python比较陌生，所以在效率方面并不大，这就是为什么当我编写两种算法来搜索元素时感到惊讶的原因

''' 
Making an array with data that can be stored easily
Setting up pointers in data using lists


 '''

import time

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] #starting / defining the array i need for the binary seach to work
process_arr = []
ctr = 0


def ARR_SEARCH(INPUT):
    start = time.time()
    # Have to set R and L in order to find the middle element of this
    l = 0
    r = len(arr)-1
    mid = None
    returntup = None
    while r > l:
        mid = (l+ (r-l))//2 # The R - L is to ensure that it is the mid
        if(arr[mid] == INPUT):
            end = time.time() - start
            r = 0
            returntup = mid, end
        elif(arr[mid] > INPUT):

            r = mid-1

        elif(arr[mid] < INPUT):

            l = mid+1

    if returntup!=None:
        return returntup
    else:
        return -1, 0


def binarySearch (arr, l, r, x): 
    start = time.time()
    # Check base case 
    if r >= l: 

        mid = l + (r - l)//2

        # If element is present at the middle itself 
        if arr[mid] == x: 
            end = time.time() - start
            print("BINARY END ", end)
            returntup = mid, end
            return returntup

        # If element is smaller than mid, then it  
        # can only be present in left subarray 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 

        # Else the element can only be present  
        # in right subarray 
        else: 
            return binarySearch(arr, mid + 1, r, x) 

    else: 
        # Element is not present in the array 
        return -1

def BRUTE_FORCE_v2(INPUT):
    start = time.time()
    ctr = -1
    for i in arr:
        ctr += 1
        if i==INPUT:
            end = time.time() - start
            print("BRUTE END" , end)
            returntup = ctr, end
            return returntup
        else:
            continue
    else:
        end = time.time() - start
        returntup = -1, end
        return returntup


def BRUTE_FORCE(INPUT):
    start = time.time()
    for i in range(len(arr)):
        if arr[i]==INPUT:
            end = time.time() - start
            returntup = i, end
            return returntup
        else:
            continue
    else:
        end = time.time() - start
        returntup = -1, end
        return returntup

search = int(input("Enter the required search element"))
out1 = BRUTE_FORCE(search)
out2 = binarySearch(arr, 0, (len(arr)-1), search)
out3 = BRUTE_FORCE_v2(search)
diff1 = out1[1] - out2[1]
diff2 = out1[1] - out3[1]
diff3 = out3[1] - out2[1]
print("Brute vs Force Ratio in this case is: \n \n ", diff1)
print("\n \n \n \n ")
print("The difference between the normal and the upgraded brute force algorithm in this case is: \n \n", diff2)
print("\n \n \n \n ")
print("So, the effective time differnece between the two actual algs are: \n \n ", diff3)

该程序的输出如下

Enter the required search element8

BINARY END  1.430511474609375e-06

BRUTE END 2.6226043701171875e-06

Brute vs Force Ratio in this case is:

5.7220458984375e-06 

The difference between the normal and the upgraded brute force algorithm in this case is:
 4.5299530029296875e-06 

So, the effective time differnece between the two actual algs are:

 1.1920928955078125e-06 

这很有意义，即使对于很小的列表，二进制搜索也会胜过蛮力

BUT

这里有趣的是，当我搜索元素'1'时

1位于列表的开头，理想情况下，蛮力应该首先找到它。但二进制搜索以某种方式胜过它

我的输出，当我搜索1时是这个

Enter the required search element1

BINARY END  1.430511474609375e-06

BRUTE END 2.86102294921875e-06

Brute vs Force Ratio in this case is: 

5.245208740234375e-06 

The difference between the normal and the upgraded brute force algorithm in this case is: 3.814697265625e-06 
So, the effective time differnece between the two actual algs are: 
1.430511474609375e-06   

[如果您想知道为什么有两种蛮力算法，一种是迭代遍历列表的python实现，一种是常规数组解析实现

我正在计算列表解析的python实现之间的差异，因为它看起来比其他实现更快，并且找到了时间之间的差异。

事实上，简单，因为蛮力只需要进行一次比较，它必须比二进制搜索要快，但是为什么不是呢？

有人可以回答这个问题吗？

PS：此代码在空闲时不能很好地播放，并且在所有结束时间输出0.0。终端似乎可以提供正确的输出。...

Answer 1

如@ kaya3所述

这确实是一个时钟错误。看起来第一个结果是偶然的，并且检查了更多的迭代次数，或者使用提到的库提供了所需的值。