(2022.06.01 Wed)
从一个序列中找到特定的元素，或离某个元素最近的位置，是对序列排序之后面临的最重要的工作之一。顺序统计学(order statistics)中，选择问题被定义为在一个非排序(unsorted)序列中，找到第个大/小的元素。
选择问题的第一步可以先对混乱序列做排序，采用常规的排序法，可以实现的复杂度。接下来是选择，在已经经过排序的序列中找到特定元素，最坏情况的复杂度是
。这里我们关注的问题是能否将选择复杂度降低。
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用于找出中间indexmid。注意，这里执行了整除操作//，向下取整。 - 如果目标值
k与中间index对应值相同，则查找完成，返回中间indexmid - 如果目标值比中间index
mid对应的值大，则由[mid, high]标记的右边序列作为下一次查找的范围；反之，则由[low, mid]标记。注意在选定右边/左边序列作为下一次查找范围时，中间index设定的边界需要调整1，以避免取mid做取整操作带来的误差。下面案例专门讲解这个误差。 - 考虑到在调整查找范围时，中间index
mid都经过加/减1的调整，这在特殊情况下会导致递归过程中high、low值的关系反转，出现这种情况意味着值k在a中不存在，因此有了代码中的第一个判断high>low。
为什么选定下一次查询范围时不能用
mid值，而要对该值做调整？
考虑下面的案例，，
。第一次调用时
，
，在
计算过程中，
，对应的元素是5。此时，如果直接用
mid(而非mid-1)作为下一次调用的high，会得到，再下一次会调用
。此时，
，直接使用
mid做下一次调用的边界而不对mid做加/减操作，则会陷入时，
，此时将
mid作为下限相当于将low作为下限，因此陷入无尽的循环。流程表示为应对这种情况，在选定下一次的查询范围时，对
mid做加/减1调整。加/减1调整之后，low的值加1，与high相同，有，在进行下次递归时，或者
mid-1作为上限，或者mid+1作为下限，则在下一次递归时会出现的情况，这种情况也就是代码需要首先处理的
，证明值
k不在序列a中。流程表示为
二分法使得在ordered array中查找复杂度从降到了
。
Randomized Quick-Selection随机快速查找
略
Reference
1 Data Structures and Algorithms in Python, Goodrich and etc
