二分搜索与线性搜索

Question

我有以下二进制搜索的实现：

import time
numbers_one_to_hundred=[]
for num in range(1,100001,2): #25 66 35 64 (38,101) (1,101)
    numbers_one_to_hundred.append(num)

print('Please choose a number:')    
my_number=int(input())

print('Length array:',len(numbers_one_to_hundred))
#print('array:',numbers_one_to_hundred)
my_start_time = time.time()
start=0
end=len(numbers_one_to_hundred)
temp_arr=numbers_one_to_hundred
index_start=start
index_end=end
index_middle=int((index_end+index_start)/2)
found=False
while(not(start==0 and start==end)):
  if temp_arr[int((end+start)/2)]==my_number: #middle temp is my number
        print('you find',temp_arr[int((end+start)/2)],'index:',index_middle)
        found=True
        break
  elif my_number<temp_arr[int((end+start)/2)]: #number in first half
        end=int((start+end)/2)
        temp_arr=temp_arr[start:end] 
        start=0
        index_end=index_middle+1
        index_middle=int((index_middle+index_start)/2)
  elif my_number>temp_arr[int((end+start)/2)]: #number in second half
        start=int((end+start)/2)        
        temp_arr=temp_arr[start+1:end] 
        start=0
        end=int((end-1)/2) 
        index_start=index_middle+1
        index_middle=int((index_end+index_middle)/2)

if not(found): #number not in list
  print('Number not in list!')
  
my_end_time = time.time()

print('passed:',my_end_time-my_start_time)

当输入为例如 50003 时，这是结果：

Please choose a number:
50003
Length array: 50000
you find 50003 index: 25001
passed: 0.0028307437896728516

这是线性搜索的代码：

import time
numbers_one_to_hundred=[]
for num in range(1,100001,2): #25 66 35 64 (38,101) (1,101)
    numbers_one_to_hundred.append(num)

print('Please choose a number:')    
my_number=int(input())

print('Length array:',len(numbers_one_to_hundred))

my_start_time=time.time()  
if my_number in numbers_one_to_hundred:
    print('SUCCESS!')

else:
    print('NOT SUCCESS!')

my_end_time = time.time()    
print('passed:',my_end_time-my_start_time)

这次搜索的结果是：

Please choose a number:
50003
Length array: 50000
SUCCESS!
passed: 0.0006299018859863281

我的问题是，为什么在这种情况下线性搜索有优势？（而且差异很大）其中一个实现有问题吗？还是输入有问题？（我尝试了 3-4 种不同的输入，所有这些输入的优势在于线性搜索）或者别的什么？

Answer 1

二分查找复制列表中的部分内容，例如 temp_arr=temp_arr[start:end]。由于此复制发生在指数衰减部分（例如，如果原始列表为 128，则下一个副本为 64，下一个为 32，等等），其总成本为 O(N) 运行算法。

编辑：澄清上述指数衰减的总成本。在所有迭代中复制列表部分的总成本为 N /2 + N /4 + N /8 + ... + 1，这是一个几何级数，等于 N-1。由于通常列表的长度不是2的幂，所以总成本会有轻微的变化，但仍然是O(N)。

虽然“二分搜索”和线性搜索的低效实现都是 O(N)，但“二分搜索”的常数因子更高，因为它使用比线性搜索更多的操作来实现其目标。所以总的来说你的“二进制搜索”比较慢。

为了使代码运行更快，想办法避免创建新列表。一种可能的解决方案是更改代码，使 start 和 end 指向原始 numbers_one_to_hundred 列表，而无需创建 temp_arr

编辑：关于改进的澄清：在不复制部分列表的情况下，对于任何具有足够元素的列表，二进制搜索应该明显更快。 cut-off 大小可能在 N=10 和 N=100 之间，当我猜测在 python.

中正确实施二分搜索时，数字接近 20

Answer 2

一个可能的解释是您的数据集不够大，二分搜索的算法优势无法克服使用 built-in 搜索与在 Python 解释器.

首先，使用更大的数据集，以便线性搜索花费大量时间：

import time
numbers = list(range(100000000))

print('Please choose a number:')    
my_number=int(input())

print('Length array:',len(numbers))

start_time = time.time()  
if my_number in numbers:
    print('SUCCESS!')
else:
    print('NOT SUCCESS!')

print('passed:', time.time() - start_time)

% python test.py
Please choose a number:
99999999
Length array: 100000000
SUCCESS!
passed: 0.9459362030029297

% python test.py
Please choose a number:
5
Length array: 100000000
SUCCESS!
passed: 0.0

上面的输出让我们确认这确实是一个需要可测量时间的线性搜索 -- 搜索列表开头的项目非常快，搜索列表末尾的项目列表大约需要一秒钟。

现在让我们对三个选项进行适当的比较——原生 in 关键字、通过解释器中的 for 循环实现的线性搜索和二进制搜索。（我将快速编写我自己的二进制搜索，而不是复制和粘贴你的——希望这个例子能告诉你如何比较不同二进制搜索实现的性能，就像我比较不同的二进制搜索实现的性能一样。线性搜索实现。）

import time
numbers = list(range(100000000))

def native_search(n):
    return n in numbers

def linear_search(n):
    for i in numbers:
        if i == n:
            return True
    return False

def binary_search(n):
    start, end = 0, len(numbers) - 1
    while True:
        mid = (start + end) // 2
        assert numbers[start] <= numbers[mid] <= numbers[end], "List isn't sorted!"
        if numbers[mid] == n:
            return True
        if start == end:
            return False
        if numbers[mid] > n:
            end = mid
        else:
            start = max(mid, start + 1)


print('Array length:', len(numbers))
print('Please choose a number:')    
my_number=int(input())

for func in (native_search, linear_search, binary_search):
    start_time = time.time()  
    print(f"{func.__name__}: {'NOT ' if not func(my_number) else ''}SUCCESS!")
    print('passed:', time.time() - start_time)

Array length: 100000000
Please choose a number:
99999999
native_search: SUCCESS!
passed: 0.9317595958709717
linear_search: SUCCESS!
passed: 2.556478500366211
binary_search: SUCCESS!
passed: 0.0009658336639404297

% python test.py
Array length: 100000000
Please choose a number:
50000000
native_search: SUCCESS!
passed: 0.47462892532348633
linear_search: SUCCESS!
passed: 1.4169631004333496
binary_search: SUCCESS!
passed: 0.0009737014770507812

我们可以看到“原生”线性搜索比使用 for 循环的版本快 2.5 倍——这是因为它是在 Python 解释器内部完成的（在 compiled/optimized 代码）而不是 Python 正在解释的代码。

但是二分查找绝对让他们都望尘莫及！我的实现和你的实现之间的性能差异可能是你在你的版本中使用的 temp_arr —— 如果你消除它，我怀疑你会看到显着的加速。

Answer 3

我认为这是因为二分查找代码比线性查找长，他们的时间不同，而线性查找时间较短，因为它的操作较少。您可以优化二进制搜索代码并使用递归方法实现它以获得更好的性能。

二分搜索与线性搜索

Binary search vs linear search

python

binary-search

linear-search