from typing import List
from typing import Tuple


def find_first_last(
    linecount: int, cache: List[Tuple[int, str]], b_state_to_find: str
) -> Tuple[List[Tuple[int, str]], int, int]:
    """
    Speed up a binary search by using a cache of what states we have seen where in the file. Use this
    cache to return a narrowed down first and last line numbers to search.

    Args:
        linecount: the number of lines in the file
        cache: a list of (offset, state) tuples in the file
        b_state_to_find: binary form of the state to find

    Returns:
        an updated cache list
        the first line number to search
        the last line number to search
    """
    cache.sort()
    first = 0
    last = linecount - 1
    to_delete = 0
    # logger.info("find_first_last for %s with cache\n%s" % (b_state_to_find, pformat(cache)))

    for (offset, state) in cache:

        if state < b_state_to_find:
            to_delete += 1
            first = offset
            # logger.info("state %s < b_state_to_find %s, to_delete %d, first %s" % (state, b_state_to_find, to_delete, first))

        elif state == b_state_to_find:
            first = offset
            last = offset
            # logger.info("state %s == b_state_to_find %s, to_delete %d, first %s, last %s" % (state, b_state_to_find, first, last))
            break

        else:
            last = offset
            # logger.info("state %s > b_state_to_find %s, last %s" % (state, b_state_to_find, last))
            break

    to_delete -= 1

    if to_delete > 0:
        cache = cache[to_delete:]

    # logger.info("find_first_last for %s, deleted %s, first %s, last %s, cache\n%s" % (b_state_to_find, to_delete, first, last, pformat(cache)))
    return (cache, first, last)