Искать конкретный кортеж в списке кортежей, отсортированных по первому элементу?

Вы действительно можете использовать модуль bisect, чтобы найти индекс кортежа с указанным вами идентификатором.

import bisect
# sorting
records_by_id = [(0, 'bubble4'), (3, 'bubble5'), (4, 'bubble3'), (5, 'bubble2'), (10, 'bubble1')]

# id you wanna find
target_id = 4

# create a list of the first ids from the tuples
ids = [x[0] for x in records_by_id]

# use bisect_left to find the index where the target_id would be inserted to maintain sorted order and check if the id at that index is the target_id
index = bisect.bisect_left(ids, target_id)
if index < len(records_by_id) and records_by_id[index][0] == target_id:
    print(f"Found at index: {index}")
else:
    print("Not found")

Вы недалеко от фактического решения. Поскольку вы уже отсортировали список по первому элементу кортежа, вы действительно можете использовать модуль bisect, чтобы найти индекс кортежа по первому его элементу.

import bisect

def find_tuple_index(sorted_list, target_id):
    index = bisect.bisect_left(sorted_list, (target_id,))
    if index < len(sorted_list) and sorted_list[index][0] == target_id:
        return index
    return -1  # Not found

# Your sorted list
records_by_id = [(0, 'bubble4'), (3, 'bubble5'), (4, 'bubble3'), (5, 'bubble2'), (10, 'bubble1')]

# Search for the tuple with id 4
result = find_tuple_index(records_by_id, 4)
print(result)  # Output: 2

Позвольте мне немного подробнее рассказать о коде.

• Сначала мы используем bisect.bisect_left(), чтобы найти точку вставки для целевого идентификатора. Эта функция работает, потому что наш список сортируется по первому элементу каждого кортежа.

• Теперь bisect_left() возвращает самое левое место в списке, куда мы можем вставить целевое значение, сохраняя порядок сортировки.

• Затем мы проверяем, находится ли найденный индекс в границах списка и соответствует ли первый элемент кортежа по этому индексу нашему целевому идентификатору.

• Если совпадение есть, мы возвращаем индекс, в противном случае мы возвращаем -1, чтобы сказать, что элемент не найден.

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

Обновлено: сложность подхода составляет O (log n), кстати.

Повторно используйте ключ сортировки для разделения пополам:

from bisect import bisect_left

records_by_id = [(10, 'bubble1'), (5, 'bubble2'), (4, 'bubble3'), (0, 'bubble4'), (3, 'bubble5'),]

key = lambda x: x[0]
records_by_id.sort(key=key)

index = bisect_left(records_by_id, 4, key=key)

print(index)

Попробуйте это онлайн!

Если возможно, что данное число не встречается, добавьте в конце проверку, проверяющую, действительно ли оно встречается по результирующему индексу.

import bisect

records_by_id = [(0, 'bubble4'), (3, 'bubble5'), (4, 'bubble3'), (5, 'bubble2'), (10, 'bubble1')]

def find_tuple_index(records, target_id):
    # Create a list of just the IDs for binary search
    ids = [record[0] for record in records]
    
    # Use bisect to find the insertion point
    index = bisect.bisect_left(ids, target_id)
    
    # Check if the index is valid and the ID matches
    if index != len(records) and records[index][0] == target_id:
        return index
    return -1  # Not found

# Example usage
target_id = 4
result_index = find_tuple_index(records_by_id, target_id)
print(f"Tuple with ID {target_id} found at index: {result_index}")

Учитывая целевой идентификатор (например, 4), мне нужно эффективно найти индекс соответствующего кортежа в этом списке. В этом случае я хочу найти индекс

(4, «пузырь3»)

Линейный поиск не идеален, поскольку список уже отсортирован. И мы используем биссектрису.

Мой ответ импортирует биссектрису и использует

биссект.бисект.левый()

чтобы найти точку выхода целевого идентификатора.

Проверяет, действителен ли найденный индекс и соответствует ли идентификатор целевому индексу, возвращает индекс найден или -1, если нет.