在按第一个元素排序的元组列表中搜索特定的元组?

重复使用排序键进行平分:

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)

Attempt This Online!

如果给定的数字可能没有出现,请在末尾添加一个检查,检查它是否确实出现在结果索引处。

您确实可以使用平分模块来查找具有给定id的元组的索引。

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

让我详细解释一下代码。

• 首先,我们使用平分线.平分线_left()来查找目标ID的插入点。此函数有效,因为我们的列表是按每个元组的第一个元素排序的。

• 现在 bisect_left() 返回列表中最左侧的位置,在那里我们可以插入目标值,同时保持排序顺序。

• 然后,我们检查找到的索引是否在列表边界内,以及该索引处的元组的第一个元素是否与我们的目标ID匹配。

• 如果有匹配项,则返回索引,否则返回-1表示未找到该项。

顺便说一句,我假设你列表中的ID是唯一的。如果你可能有重复的ID,你需要修改函数来处理这种情况,也许是通过返回所有匹配索引的列表。

编辑:该方法的复杂性在于 O(对数n) 顺便说一句

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}")

给定一个目标ID(例如4),我需要有效地找到此列表中相应元组的索引。在这种情况下,我想找到索引

(4,“气泡3”)

线性搜索并不理想,因为列表已经排序。我们使用平分线。

我的答案导入平分并使用

平分线.平分线.左()

以找到目标ID的搜索点。

检查找到的索引是否有效,如果ID与目标匹配,则返回找到索引,否则返回-1。