在有序数组上的二进制和线性搜索，为什么二进制搜索要比线性搜索更长？

Question

here是一个最小的可复制示例：

import time 
import random
''''
search algorithms for ORDERED arrays 

linear search
binary search 

'''
def timeit(f):
    def wrapper(*args, **kwargs):
        st = time.time()
        y =f( *args,**kwargs)
        ft = time.time()
        print(f.__name__,'\n', ft-st, 'seconds')
        print("searching for value: ", args[1], f"\nsize of search space: {len(args[0])} elements",  f'\nfound? @ idx={y}')
        if y:
            print("verifying...")
            print(f"x[{y}]={x[y]}\n\n")
        return y
    return wrapper 
    
    
def sample_array(n=10000000, type=['classic','ordered'][1]):
    if type == 'classic':
    return list(random.choices( list(range(1,101)),k=n))
    if type == 'ordered':
    return sorted(list(random.choices( list(range(1,101)),k=n)))
    
    


@timeit 
def linear_search(x,val):
    '''
    x : ordered array 
    val: search value 
    '''
    if x[0] > val or val > x[-1]: # check if out of bounds
        return None  
    for (idx, _val) in enumerate(x): # check part of array 
    
    if _val == val:
        return idx  
    else:
        return None 

@timeit     
def binary_search(x,val):
    '''
    x: ordered array 
    val: search value
    '''
    if x[0] > val or val > x[-1]: # check if out of bounds 
    return None 
    x = list(enumerate(x)) # tracking indices of total array
    
    while True:
    mid = len(x)//2
    if x[mid][1] == val:
        return x[mid][0]

    elif val < x[mid][1]:
        x = x[:mid]
            
    elif val > x[mid][1]:
        x = x[mid:]
        
    # base case     
    if len(x) == 2:
        if all([_x[1] != val for _x in x ] ):
            return None 
                            
                                
        
x = sample_array()
linear_search(x,68)
idx= binary_search(x,68)

我希望我的二进制搜索实施有问题。有人能发现这个问题吗？

我一直在努力弄清楚如何返回正确的二进制搜索索引（如果有），所以我觉得这与我的实现有关。

有人可以提供帮助吗？

我希望在大型搜索空间上进行二进制搜索所花费的时间比线性搜索要快，但是我得到了相反的结果。
    

代码的最大问题是，由于缩进错误，它不会编译。假设有可编译的凹痕如下：

linear_search

如果所寻求的值不在索引0，则放弃并返回。这应该是：

    '''
    x : ordered array 
    val: search value 
    '''
    if x[0] > val or val > x[-1]: # check if out of bounds
        return None  
    for (idx, _val) in enumerate(x): # check part of array   
        if _val == val:
            return idx  
        else:
            return None 

Answer 1

，但我们可以使它更加有效，因为我们知道数组已排序：

None

代码的其他问题： 线性和二进制搜索的运行时间仅在排序数组时才有意义，这是二进制搜索所需的。

如果数组未排序，请勿使用二进制搜索！

您的装饰器假设函数

    '''
    x : ordered array 
    val: search value 
    '''
    if x[0] > val or val > x[-1]: # check if out of bounds
        return None  
    for (idx, _val) in enumerate(x): # check part of array     
        if _val == val:
            return idx  
    return None 

被装饰是两个参数的函数，即数组和值，并且正在返回索引。将论点定义为使用

def linear_search(arr, val):
    '''
    arr : ordered array
    val: search value
    '''
    if arr[0] > val or val > arr[-1]: # check if val does not exist in
        return None

    for (idx, _val) in enumerate(arr): # check part of array
        if _val == val:
            return idx
        if _val > val:
            return None

    raise AssertionError("There is no way we should arrive here if the list is sorted.")

和

timeit

的

f

将论点定义为

wrapper
1. 确实没有意义。此功能还应执行n迭代，以使用*args。
您的二进制搜索可以大大简化，并且更有效。 您的输入阵列为10000000个元素。当我们搜索恰好位于非常低索引的值时，线性搜索的性能不会太差。但是，当所寻求的值处于较高的索引时，线性和二进制搜索之间的性能差异是巨大的。两种测试都应进行。同样，如果数组只有100个不同的值，则具有相同值的平均1000000索引。本质上，您平均仅搜索100个值的数组。应使用所有不同数组值进行适当的测试。 我修改了代码的其他方面，例如更好的参数和可变名称。我建议您查看每条代码，并查看我所做的更改。

2. **kwargs

   Prints：

   time.perf_counter