如何实现将整数列表四分后对每个切片应用双向搜索的函数？

问题分析 #

你需要的fourslicebidirectionSearch()函数核心逻辑是：将列表分割为四个切片，对每个切片独立执行双向搜索，而非同步遍历切片的同一索引位置。原FourSliceSearch的逻辑不符合双向搜索的要求，且原BiDirectionSearch存在未检查中间元素的bug。

修复与实现代码 #

首先修复双向搜索函数的bug，确保能覆盖所有元素，再实现四分切片的双向搜索：

def BiDirectionSearch(key, ls):
    i = 0
    j = len(ls) - 1
    loop_count = 0
    # 改为i <= j，确保中间元素被检查
    while i <= j:
        loop_count += 1
        if ls[i] == key:
            return True, loop_count, i  # 返回切片内的索引，方便计算原列表位置
        if ls[j] == key:
            return True, loop_count, j
        i += 1
        j -= 1
    return False, loop_count, -1

def fourslicebidirectionSearch(key, ls):
    total_length = len(ls)
    slice_size = total_length // 4
    # 分割四个切片，处理长度非4倍数的情况
    slices = [
        ls[0:slice_size],
        ls[slice_size:2*slice_size],
        ls[2*slice_size:3*slice_size],
        ls[3*slice_size:]
    ]
    total_loop = 0
    # 逐个切片执行双向搜索
    for slice_idx, current_slice in enumerate(slices):
        found, loop_count, pos_in_slice = BiDirectionSearch(key, current_slice)
        total_loop += loop_count
        if found:
            # 计算目标在原列表中的位置
            original_pos = slice_idx * slice_size + pos_in_slice
            return True, total_loop, original_pos
    # 所有切片均未找到目标
    return False, total_loop, -1

# 测试代码
myNum2 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
key = 9

# 测试各函数
result_bi, loop_bi, pos_bi = BiDirectionSearch(key, myNum2)
result_four, loop_four, pos_four = fourslicebidirectionSearch(key, myNum2)
result_old, loop_old = FourSliceSearch(key, myNum2)

if result_four:
    print(f'{key} 在列表中找到')
    print(f'全列表双向搜索：循环 {loop_bi} 次，位置 {pos_bi+1}')
    print(f'四分双向搜索：循环 {loop_four} 次，位置 {pos_four+1}')
    print(f'原四分搜索：循环 {loop_old} 次')
else:
    print(f'{key} 不在列表中，总循环 {loop_four} 次')

代码说明 #

1. 修复后的BiDirectionSearch：

   • 调整循环条件为i <= j，避免遗漏列表中间的元素
   • 新增返回切片内的索引，用于计算目标在原列表中的位置
   • 准确统计每次循环的次数

2. fourslicebidirectionSearch：

   • 按长度均分列表为四个切片，自动处理长度非4倍数的情况（最后一个切片包含剩余元素）
   • 对每个切片依次执行双向搜索，累计总循环次数
   • 找到目标后，计算其在原列表中的位置并返回；若所有切片均未找到，返回未找到状态和总循环次数

3. 原FourSliceSearch的问题：
   该函数是同步遍历四个切片的相同索引位置，并非对每个切片应用双向搜索，无法发挥双向搜索从两端同时查找的效率优势，逻辑不符合需求。

内容的提问来源于stack exchange，提问作者Silver Haunter