选择/查找selection, since 2022-06-01

作者: Mc杰夫 | 来源:发表于2022-06-01 11:31 被阅读0次

(2022.06.01 Wed)
从一个序列中找到特定的元素，或离某个元素最近的位置，是对序列排序之后面临的最重要的工作之一。顺序统计学(order statistics)中，选择问题被定义为在一个非排序(unsorted)序列中，找到第 $k$ 个大/小的元素。

选择问题的第一步可以先对混乱序列做排序，采用常规的排序法，可以实现 $O(nlogn)$ 的复杂度。接下来是选择，在已经经过排序的序列中找到特定元素，最坏情况的复杂度是 $O(n)$ 。这里我们关注的问题是能否将选择复杂度降低。

Prune-and-Search

也称为Decrease-and-Conquer法，这是一种算法设计模式。在该设计模式中，首先定义一个含有n个对象的集合，筛选切除该集合的一部分，并recursively对余下的部分进行处理和计算并解决要解决的问题。可以将该问题变为常数时间问题，接下来就可以采用暴力法(brute-force)解决。并回溯之前的每一步便可实现对问题的解决。有时候可以避免使用递归，而是循环使用问题分解/降解步骤，直到可以使用暴力法解决问题。二分法(binary search)就是一个案例。

二分法Binary Search

对于一个已经经过排序的序列，找出指定的元素，或序列中距离指定元素最近的位置。
问题：有order array a，和某元素k，找k在a中的index。

def binary_search(a, k, low, high):
    if high < low:
        return ((high, a[high]), (high+1, a[high+1]))
    mid = (low + high) // 2
    if k == a[mid]:
        return mid
    elif k > a[mid]:
        return binary_seach(a, k, mid+1, high)
    else:
        return binary_search(a, k, low, mid-1)

分析：

代码中的low、high分别表示备选序列的index上、下限，即a[low, high]是经过prune之后生成的序列
该算法总是从备选序列的中间开始，中间元素与目标k做比较，并根据结果缩小备选序列。代码中的mid = (low + high) // 2用于找出中间index mid。注意，这里执行了整除操作//，向下取整。
如果目标值k与中间index对应值相同，则查找完成，返回中间index mid
如果目标值比中间index mid对应的值大，则由[mid, high]标记的右边序列作为下一次查找的范围；反之，则由[low, mid]标记。注意在选定右边/左边序列作为下一次查找范围时，中间index设定的边界需要调整1，以避免取mid做取整操作带来的误差。下面案例专门讲解这个误差。
考虑到在调整查找范围时，中间index mid都经过加/减1的调整，这在特殊情况下会导致递归过程中high、low值的关系反转，出现这种情况意味着值k在a中不存在，因此有了代码中的第一个判断high>low。

为什么选定下一次查询范围时不能用mid值，而要对该值做调整？
考虑下面的案例， $a=[1, 3, 5, 7, 9]$ ， $k=4$ 。第一次调用时 $low=0$ ， $high=4$ ，在 $binary\_search(a, k, low, high)$ 计算过程中， $mid = 2$ ，对应的元素是5。此时，如果直接用mid(而非mid-1)作为下一次调用的high，会得到 $binary\_search(a, k, 0, 2)$ ，再下一次会调用 $binary\_search(a, k, 1, 2)$ 。此时， $low=1, \space high=2,\space mid = 1$ ，直接使用mid做下一次调用的边界而不对mid做加/减操作，则会陷入 $binary\_search(a, k, 1, 2)$ 这个循环无法退出。无法退出的原因在于，当 $high-low=1$ 时， $mid = (high+low) // 2 = low$ ，此时将mid作为下限相当于将low作为下限，因此陷入无尽的循环。流程表示为 $\begin{align} &\cdots \\ step \space n&: high= high_n, low=low_n, high-low = 1, \space mid = (high_n+low_n)//2=low_n \\ step \space n+1&: high = high_n, low = mid_n = low_n, \space mid_{n+1}=(high_n+low_n)//2=low_n\\ step \space n+2&: high = high_n, low = mid_{n+1} = low_n, \space mid=(high_n+low_n)//2=low_n \\ &\cdots \end{align}$ 应对这种情况，在选定下一次的查询范围时，对mid做加/减1调整。加/减1调整之后，low的值加1，与high相同，有 $low = high = mid$ ，在进行下次递归时，或者mid-1作为上限，或者mid+1作为下限，则在下一次递归时会出现 $high<low$ 的情况，这种情况也就是代码需要首先处理的 $if \space high < low$ ，证明值k不在序列a中。流程表示为
$\begin{align} & \cdots \\ step \space n&: high = high_n, \space low=low_n, \space high-low = 1, \space, mid_n= (high_n+low_n)//2 = low_n\\ step \space n+1&: high_{n+1} = high_n, low_{n+1}=mid_{n}+1=low_n+1, mid_{n+1}=(high_n+low_n+1)//2=high_n\\ step \space n+2&: high_{n+2}=high_n,\space low_{n+2}=mid_{n+1}+1=high_n+1, high_{n+2}<low_{n+2}, then \space quit \end{align}$