接借助快速排序思想，在一组无序记录中查找关键字等于key的记录

快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分小，然后分别对这两部分继续进行排序。这种分治的思想可以应用于查找操作，即快速选择（QuickSelect）。

在查找关键字等于给定 key 的记录时，我们可以利用快速排序的分区过程。首先，随机选择一个基准值（pivot），然后把数组分为两部分，小于基准的放在左边，大于或等于基准的放在右边。如果基准值正好等于 key，那么直接返回对应的索引；如果 key 小于基准，说明目标在左半部分，搜索左半部分；反之，搜索右半部分。

这里是一个简单的伪代码描述：

def quick_select(arr, left, right, key):
    if left == right:  # 如果只有一个元素，直接比较
        return left if arr[left] == key else -1

    pivot_index = partition(arr, left, right)  # 分区并获取基准的索引
    if key == arr[pivot_index]:  # 找到key
        return pivot_index
    elif key < arr[pivot_index]:  # key在左侧区域
        return quick_select(arr, left, pivot_index - 1, key)
    else:  # key在右侧区域
        return quick_select(arr, pivot_index + 1, right, key)

def partition(arr, left, right):  # 基准划分
    pivot_key = arr[right]
    i = left - 1
    for j in range(left, right):
        if arr[j] <= pivot_key:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[right] = arr[right], arr[i+1]
    return i + 1