chapters.py

    #!/usr/bin/env python3

    class Position:
        def __init__(self, file, offset):
            '''A position has both a file and offset'''
            self.file = file
            self.offset = offset

        def __lt__(self, other):
            '''Positions are ordered first by file then by offset.'''
            if self.file < other.file:
                return True
            elif self.file == other.file:
                return self.offset < other.offset
            else:
                return False

        def __eq__(self, other):
            '''Positions are equal if the file and offset are the same.'''
            return self.file == other.file and self.offset == other.offset

        def __str__(self):
            '''Pretty print for Position.'''
            return f'(file={self.file}, offset={self.offset})'


    def binary_search(data, target):
        '''Returns the index of ``target`` within the sorted list, ``data``.

        If ``target`` is not in ``data``, return the index at which it can be
        inserted to maintain sorted order.
        '''
        lo = 0
        hi = len(data)

        while 1 < hi - lo:
            mid = (hi + lo) // 2
            if target < data[mid]:
                hi = mid
            elif data[mid] < target:
                lo = mid
            else:
                assert data[mid] == target
                return mid

        return lo + 1


    if __name__ == '__main__':
        import random

        chapters = [
            Position(file=0, offset=0),
            Position(file=1, offset=85),
            Position(file=2, offset=1),
            Position(file=5, offset=33),
            Position(file=7, offset=50),
            Position(file=7, offset=51),
            Position(file=9, offset=0),
        ]

        for _ in range(25):
            file = random.randrange(10)
            offset = random.randrange(100)
            pos = Position(file, offset)
            index = binary_search(chapters, pos)
            print(f'Position {pos} is in chapter {index - 1}')

output.txt

$ ./chapters.py
Position (file=8, offset=70) is in chapter 5
Position (file=1, offset=63) is in chapter 0
Position (file=5, offset=96) is in chapter 3
Position (file=6, offset=1) is in chapter 3
Position (file=2, offset=29) is in chapter 2
Position (file=1, offset=32) is in chapter 0
Position (file=4, offset=87) is in chapter 2
Position (file=2, offset=84) is in chapter 2
Position (file=7, offset=81) is in chapter 5
Position (file=7, offset=70) is in chapter 5
Position (file=3, offset=58) is in chapter 2
Position (file=8, offset=16) is in chapter 5
Position (file=8, offset=91) is in chapter 5
Position (file=2, offset=96) is in chapter 2
Position (file=8, offset=61) is in chapter 5
Position (file=9, offset=97) is in chapter 6
Position (file=3, offset=41) is in chapter 2
Position (file=1, offset=82) is in chapter 0
Position (file=6, offset=83) is in chapter 3
Position (file=5, offset=72) is in chapter 3
Position (file=1, offset=47) is in chapter 0
Position (file=1, offset=99) is in chapter 1
Position (file=6, offset=8) is in chapter 3
Position (file=4, offset=36) is in chapter 2
Position (file=9, offset=18) is in chapter 6