时间戳

首页 > 解决方案 > 修改二分查找功能

python - 修改二分查找功能

问题描述

早上好，你可以根据最大值（最后一项）、最小值（第一项）和搜索值来估计要搜索的项的位置，而不是总是使用列表的中间进行搜索（二分查找） .

（（假设项目的均匀分布和排序的项目。））这是我下面的代码，你们有任何建议的代码吗？ 

def binary_search(seq,item):
"""It uses non recursive method to search the item in the given seq. 
   It returns the position of item if found, None otherwise"""

left_index=0
right_index=len(seq)-1
while left_index <= right_index:            #stop searching when left_index > right_indext
    mid_index=(right_index + left_index)//2 #find the mid point
    if seq[mid_index]==item:
        return mid_index
    elif seq[mid_index]>item:
        right_index = mid_index -1          #if mid point ele > search ele, move right pointer
    else:  
        left_index = mid_index + 1          #if mid point ele < search ele, move left pointer
return None
a=[1,2,3,4,5,6,7,8,9]
print(binary_search(a,6))

标签： pythonsearch

解决方案

假设物品的均匀分布并且物品被排序。

撇开二进制搜索需要排序数据而不管您在哪里选择分割点这一事实不谈，对数据做出假设的能力意味着像这样的优化是可能的。

事实上，如果您假设数据始终是1..100没有间隙的唯一数字，您可以让它更快:-)

当然，这对于一般情况并没有真正的帮助，如果你在数据集上运行你的算法，你会看到它{ 1, 2, 3, 4, 5, ..., 100, 99999999 }，寻找100.

您的算法希望在数组的早期而不是倒数第二个索引中找到它。

假设数据集属性的能力已在许多情况下成功使用。例如，在哈希查找中使用英文姓氏，您可以给出以他们自己的存储桶开头的名称，同时E将那些以 、 和 开头的Z名称集中到一个存储桶中（假设以 开头的名称比其他名称更常见） .XVYE

推荐阅读