Algorithms: binary search

Tutorials

Geeks for Geeks

https://www.geeksforgeeks.org/binary-search/

Example

def find(data: List[Dict], id_: str):
    """ Search list-of-dicts for a dict with `id_`

    Args:
        data: ``(ex: [{'id_': '0bac5130b4464968a94c5641306b347e'}, ...])``
            list of dicts

        id_: ``(ex: 'e03977d172534fd7841a0ed7c1a32f7a')``
            id you are searching for
    """
    # data must first be sorted by search-key
    sort(data, key=lambda x: x['id_'])

    # binary search
    min_ = 0
    max_ = len(data)
    while True:
        median = min_ + ((max_ - min_) // 2)
        median_id = data[median]['id_']

        if node_id == median_id:
            return data[median]

        if median in (max_, min_):
            raise IndexError('`id_` not present in `data`: {}'.format(id_))

        if node_id < median_id:
            max_ = median
        elif node_id > median_id:
            min_ = median