vertical-binary-search.py

import bisect

CHECKBOX_ENTRIES = [
    (0, 0, 'One'),
    (4, 0, 'Two'),
    (8, 0, 'Three'),
    (0, 10, 'Red'),
    (4, 10, 'Green'),
    (8, 10, 'Blue'),
    (0, 20, 'A'),
    (4, 20, 'B'),
    (8, 20, 'C'),
]

def get_nearest_checkbox(checkboxes, checkboxes_y, x, y, distance_limit):
    # binary range search for all checkboxes within Y-axis distance limit
    left, right = bisect.bisect_left(checkboxes_y, y - distance_limit), bisect.bisect_right(checkboxes_y, y + distance_limit)
    candidates = checkboxes[left:right]

    # get the nearest checkbox in the resulting candidates by Euclidean distance
    result = min(candidates, key=lambda c: (c[0] - x) ** 2 + (c[1] - y) ** 2)
    return result if (result[0] - x) ** 2 + (result[1] - y) ** 2 <= distance_limit ** 2 else None

# sort by Y-axis position
sorted_checkboxes = sorted(CHECKBOX_ENTRIES, key=lambda entry: entry[1])
sorted_checkboxes_y = [y for _, y, _ in sorted_checkboxes]

# get the Y-axis distance limit, which should be the largest possible X-axis distance
distance_limit = max(x for x, _, _ in sorted_checkboxes) - min(x for x, _, _ in sorted_checkboxes)

# search for the nearest checkbox to coordinate (3, 1) (should be the checkbox with label "Two")
print(get_nearest_checkbox(sorted_checkboxes, sorted_checkboxes_y, 3, 1, distance_limit))