基于二分查找确定字符串所在文件范围的算法求实现

核心思路 #

由于目标字符串的存在范围是连续区间，我们可以通过两次二分查找分别定位区间的左边界（第一个包含字符串的文件）和右边界（最后一个包含字符串的文件），彻底避免逐个遍历的低效问题。

伪代码实现 #

首先定义辅助检查函数：

function contains_string(file, target_str):
    return True if target_str exists in file else False

查找左边界（第一个包含目标字符串的文件）

function find_left_bound(files, target_str):
    left = 0
    right = length(files) - 1
    left_bound = -1
    while left <= right:
        mid = (left + right) // 2
        if contains_string(files[mid], target_str):
            left_bound = mid
            right = mid - 1  # 继续向左寻找更早的文件
        else:
            left = mid + 1   # 向右搜索
    return left_bound

查找右边界（最后一个包含目标字符串的文件）

function find_right_bound(files, target_str):
    left = 0
    right = length(files) - 1
    right_bound = -1
    while left <= right:
        mid = (left + right) // 2
        if contains_string(files[mid], target_str):
            right_bound = mid
            left = mid + 1   # 继续向右寻找更晚的文件
        else:
            right = mid - 1  # 向左搜索
    return right_bound

整合获取范围

function get_string_range(files, target_str):
    left = find_left_bound(files, target_str)
    if left == -1:
        return "目标字符串不存在于任何文件中"
    right = find_right_bound(files, target_str)
    return (files[left], files[right])

Python代码示例 #

def contains_string(file, target_str):
    # 替换为实际文件检查逻辑，可根据需求优化（如缓存已检查结果）
    with open(file, 'r', encoding='utf-8') as f:
        return target_str in f.read()

def find_left_bound(files, target_str):
    left, right = 0, len(files) - 1
    left_bound = -1
    while left <= right:
        mid = (left + right) // 2
        if contains_string(files[mid], target_str):
            left_bound = mid
            right = mid - 1
        else:
            left = mid + 1
    return left_bound

def find_right_bound(files, target_str):
    left, right = 0, len(files) - 1
    right_bound = -1
    while left <= right:
        mid = (left + right) // 2
        if contains_string(files[mid], target_str):
            right_bound = mid
            left = mid + 1
        else:
            right = mid - 1
    return right_bound

def get_string_range(files, target_str):
    left_idx = find_left_bound(files, target_str)
    if left_idx == -1:
        return None
    right_idx = find_right_bound(files, target_str)
    return (files[left_idx], files[right_idx])

# 使用示例
files = ["file_1.txt", "file_2.txt", "file_3.txt", "file_4.txt", "file_5.txt",
         "file_6.txt", "file_7.txt", "file_8.txt", "file_9.txt", "file_10.txt"]
target = "your_target_string"
result = get_string_range(files, target)
if result:
    print(f"目标字符串范围：{result[0]} 至 {result[1]}")
else:
    print("未找到目标字符串")

优化提示 #

• 若需搜索数千个字符串，建议缓存每个文件的内容或已检查的字符串结果，避免重复读取文件，进一步提升效率。
• 确保文件列表是按顺序排列的，且字符串存在范围为连续区间，这是二分查找有效的前提。

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