Помогите написать бинарный поиск внутри текстового файла

Есть большой текстовый файл со строками, упорядоченными по алфавиту без учёта регистра.

Нужно написать функцию, которая принимает на вход построку и выводит все строки из файл, имеющие такое начало без учёта регистра. И нужно что бы это работало максимально быстро.

То есть нужно перемещаться при помощи seek по файлу, считывать по две строки (первая будет обрезана) и вторую приводить к нижнему регистру, сравнивать с искомой и в зависимости от этого куда-либо смещаться. Таким образом необходимо найти позицию первой строки, содержащей искомую подстроку в начале и позицию последней такой строки. Между ними может быть несколько гигабайт, а поэтому если между ними слишком много символов, считывать их не нужно.

По этой же принине если в какой-то момент будет найдена строка с искомым началом, нужно продолжать использовать бинарный поиск что бы найти первую и последнюю такую строку.

У кого-нибудь есть готовое решение для этой программы? Я пробовал решить самостоятельно несколько раз, но всё время программа работала не так как нужно или медленее, чем нужно.

Вот моя первая попытка:

def find_in_text_file(ID_file, find_str, limit):
    # Открываем файл и переводим искомую строку в нижний регистр
    with open(f'part_{ID_file}.txt', encoding='utf-8') as file:
        find_str = find_str.lower()

        # Инициализируем переменные
        first_pos = 0
        last_pos = file.seek(0, 2)  # устанавливаем последнюю позицию на конец файла
        num_lines = 0
        results = []

        # Бинарный поиск
        while first_pos < last_pos:
            mid_pos = (first_pos + last_pos) // 2
            file.seek(mid_pos)
            file.readline()  # переходим на начало следующей строки

            # Считываем две строки и ищем вторую строку, начинающуюся с искомой подстроки
            line1 = file.readline().lower()
            line2 = file.readline().lower()
            if line2.startswith(find_str):
                # Ищем первую и последнюю позиции, содержащие искомую подстроку
                start_pos = mid_pos + len(line1)
                end_pos = start_pos + len(line2)
                while True:
                    file.seek(start_pos - 1)
                    if file.read(1) == '\n':
                        break
                    start_pos -= 1
                while True:
                    file.seek(end_pos)
                    if file.read(1) == '\n' or end_pos == last_pos:
                        break
                    end_pos += 1

                # Оцениваем количество строк между первой и последней позицией
                num_lines = (end_pos - start_pos) // 86 + 1
                if num_lines <= limit:
                    # Если строк меньше или равно лимиту, добавляем их в список результатов
                    file.seek(start_pos)
                    results = [line.strip() for line in file.readlines(num_lines)]
                else:
                    # Если строк больше лимита, возвращаем ошибку
                    return ["Error. Many result", num_lines]
                
                # Ищем последнюю позицию, содержащую искомую подстроку
                last_found_pos = end_pos
                while last_found_pos < last_pos:
                    file.seek(last_found_pos)
                    line = file.readline().lower()
                    if line.startswith(find_str):
                        last_found_pos += len(line)
                    else:
                        break
                
                # Устанавливаем начальную позицию для следующего поиска
                first_pos = end_pos
                
            elif line2 > find_str:
                last_pos = mid_pos
            else:
                first_pos = mid_pos + len(line1)
        
        if results:
            return results
        else:
            return ["Not found"]

И вот вторая попытка:

def find_in_big_file(name_file, find_str, limit):
    find_str = find_str.lower()
    sr_len_string = 86  # средняя длина строки
    with open(f"{name_file}", "r", encoding="utf-8", errors='ignore') as f:
        f.seek(0, 2)
        size = f.tell()
        f.seek(0)
        low, high = 0, size
        while low < high:
            mid = (low + high) // 2
            f.seek(mid)
            f.readline()
            line = f.readline().lower()
            if line.startswith(find_str):
                start_pos = mid
                break
            elif line < find_str:
                low = mid + 1
            else:
                high = mid
        else:
            return []
        f.seek(0)
        low, high = 0, size
        end_pos=-1
        while low < high-500:
            mid = (low + high) // 2
            f.seek(mid)
            f.readline()
            line = f.readline().lower()
            #print(low,high,line)
            #print()
            if line.startswith(find_str):
                end_pos = mid
                low = mid + 1
            elif line < find_str:
                low = mid + 1
            else:
                high = mid
        f.seek(max(start_pos-5000,0))
        result = []
        count = 0
        if end_pos == -1:
            end_pos = high

        count_lines = round((end_pos-start_pos)//sr_len_string)
        if count_lines > limit:
            return(["Error. Many result", count_lines])
        data = f.read((end_pos-start_pos) + 10000).split('\n')[1:-1]
        #print(data)
        for d in data:
            if d.lower().startswith(find_str):
                result.append(d)
                count += 1
                if count > limit:
                    return ["Error. Many result", count]
    return result