博客

Python实现简单的索引排序与搜索功能

  • Post category:Python

对于Python实现简单的索引排序与搜索功能，可以分为以下几个步骤：

1. 准备工作

首先准备一个包含数据的列表或者字典，这些数据需要有一些关键字。以一个包含学生信息的字典列表为例子。

students=[
    {"name": "Tom", "age": 18, "gender": "male", "score": 98},
    {"name": "Jenny", "age": 21, "gender": "female", "score": 80},
    {"name": "Alice", "age": 20, "gender": "female", "score": 85},
    {"name": "Bob", "age": 19, "gender": "male", "score": 90},
]

2. 索引排序

接下来，我们需要对这些数据进行排序，并且创建一个索引，使得可以按照指定的关键字进行快速搜索。Python中的sorted函数可以进行排序，并且可以通过key参数指定排序的关键字。这里以按照成绩从高到低为例。

idx_sorted=sorted(range(len(students)),key=lambda x: students[x]["score"],reverse=True)

这里使用了一个lambda函数作为key参数，用于指定排列的依据是学生成绩。要形成索引数组，最简单的方法是使用range(len(students))，以便使得每一个索引和列表中的每一个元素一一对应。

3. 搜索功能

有了索引之后，我们可以实现简单的搜索功能。具体的做法就是在索引中二分查找。因此，我们需要先实现一个叫做binary_search的函数。该函数的基本思想就是想寻找索引段$[a,b)$中的一个键值，它要么不存在, 要么仅仅出现一次，或者出现多次。函数会根据相应的情况返回对应的结果。

def binary_search(a,b,func,flag=True):
    """
    This function is used to find the index i that satisfies a<=i<b
    and func(i) is True. func is a function of one argument. 

    When flag is True, it will return -1 if i doesn't exist;
    When flag is False, it will return the last index of 
    matching key if i doesn't exist.
    """
    if not func(a) and flag:
        return -1
    if func(b-1) and not flag:
        return b-1
    while a+1<b:
        mid=a+(b-a)//2
        if not func(mid):
            a=mid
        else:
            b=mid
    if flag:
        return b if b<len(students) and func(b) else -1
    else:
        return a if func(a) else -1

函数的参数中，参数func表示要查找的关键字，flag表示是否查找最后一个匹配的关键字（默认为True，查找第一个匹配到的关键字）。该函数会返回匹配到的元素在索引数组中的位置，如果未找到则根据flag参数返回-1或精确匹配最后一个关键字的位置。

这样，我们就可以通过二分查找来实现快速搜索。

target_name="Tom"
search_func=lambda x: students[idx_sorted[x]]["name"]>=target_name
target_idx=binary_search(0,len(idx_sorted),search_func)
if target_idx==-1 or students[idx_sorted[target_idx]]["name"]!=target_name:
    print("Not Found!")
else:
    print(students[idx_sorted[target_idx]])

4. 示例

接下来看两个完整的示例，一个是在列表中查找指定学生的信息，一个是在字典列表中查找成绩在90分以上的学生。

# 示例1：在列表中查找指定学生的信息
students=[
    {"name": "Tom", "age": 18, "gender": "male", "score": 98},
    {"name": "Jenny", "age": 21, "gender": "female", "score": 80},
    {"name": "Alice", "age": 20, "gender": "female", "score": 85},
    {"name": "Bob", "age": 19, "gender": "male", "score": 90},
]

# 创建索引
idx_sorted=sorted(range(len(students)),key=lambda x: students[x]["score"],reverse=True)

# 查找Tom的信息
target_name="Tom"
search_func=lambda x: students[idx_sorted[x]]["name"]>=target_name
target_idx=binary_search(0,len(idx_sorted),search_func)
if target_idx==-1 or students[idx_sorted[target_idx]]["name"]!=target_name:
    print("Not Found!")
else:
    print(students[idx_sorted[target_idx]])

# 示例2：在字典列表中查找成绩在90分以上的学生
students=[
    {"name": "Tom", "age": 18, "gender": "male", "score": 98},
    {"name": "Jenny", "age": 21, "gender": "female", "score": 80},
    {"name": "Alice", "age": 20, "gender": "female", "score": 85},
    {"name": "Bob", "age": 19, "gender": "male", "score": 90},
]

# 创建索引
idx_sorted=sorted(range(len(students)),key=lambda x: students[x]["score"],reverse=True)

# 查找成绩在90分以上的学生
search_func=lambda x: students[idx_sorted[x]]["score"]>=90
target_idx=binary_search(0,len(idx_sorted),search_func)
if target_idx==-1:
    print("Not Found!")
else:
    print([students[idx_sorted[i]] for i in range(target_idx,len(idx_sorted))])

以上就是简单的索引排序与搜索功能实现的完整攻略，希望对你有所帮助。

Tags: ,