(2022.06.01 Wed)
從一個序列中找到特定的元素丈咐，或離某個元素最近的位置，是對序列排序之后面臨的最重要的工作之一龙宏。順序統(tǒng)計學(order statistics)中棵逊，選擇問題被定義為在一個非排序(unsorted)序列中，找到第個大/小的元素银酗。
選擇問題的第一步可以先對混亂序列做排序辆影，采用常規(guī)的排序法，可以實現(xiàn)的復雜度黍特。接下來是選擇蛙讥，在已經(jīng)經(jīng)過排序的序列中找到特定元素，最壞情況的復雜度是
灭衷。這里我們關注的問題是能否將選擇復雜度降低次慢。
Prune-and-Search
也稱為Decrease-and-Conquer法，這是一種算法設計模式。在該設計模式中迫像，首先定義一個含有n個對象的集合劈愚，篩選切除該集合的一部分，并recursively對余下的部分進行處理和計算并解決要解決的問題闻妓【穑可以將該問題變?yōu)槌?shù)時間問題，接下來就可以采用暴力法(brute-force)解決纷闺。并回溯之前的每一步便可實現(xiàn)對問題的解決算凿。有時候可以避免使用遞歸，而是循環(huán)使用問題分解/降解步驟犁功，直到可以使用暴力法解決問題氓轰。二分法(binary search)就是一個案例。
二分法Binary Search
對于一個已經(jīng)經(jīng)過排序的序列浸卦，找出指定的元素署鸡，或序列中距離指定元素最近的位置。
問題：有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]是經(jīng)過prune之后生成的序列 - 該算法總是從備選序列的中間開始稚叹，中間元素與目標
k做比較焰薄，并根據(jù)結(jié)果縮小備選序列。代碼中的mid = (low + high) // 2用于找出中間indexmid扒袖。注意塞茅，這里執(zhí)行了整除操作//，向下取整季率。 - 如果目標值
k與中間index對應值相同野瘦，則查找完成，返回中間indexmid - 如果目標值比中間index
mid對應的值大飒泻，則由[mid, high]標記的右邊序列作為下一次查找的范圍鞭光；反之，則由[low, mid]標記泞遗。注意在選定右邊/左邊序列作為下一次查找范圍時惰许，中間index設定的邊界需要調(diào)整1，以避免取mid做取整操作帶來的誤差刹孔。下面案例專門講解這個誤差啡省。 - 考慮到在調(diào)整查找范圍時娜睛，中間index
mid都經(jīng)過加/減1的調(diào)整，這在特殊情況下會導致遞歸過程中high卦睹、low值的關系反轉(zhuǎn)畦戒，出現(xiàn)這種情況意味著值k在a中不存在，因此有了代碼中的第一個判斷high>low结序。
為什么選定下一次查詢范圍時不能用
mid值障斋，而要對該值做調(diào)整？
考慮下面的案例徐鹤，垃环，
。第一次調(diào)用時
返敬，
遂庄，在
計算過程中，
劲赠，對應的元素是5涛目。此時，如果直接用
mid(而非mid-1)作為下一次調(diào)用的high凛澎，會得到霹肝，再下一次會調(diào)用
。此時塑煎，
沫换，直接使用
mid做下一次調(diào)用的邊界而不對mid做加/減操作，則會陷入時，
炭晒，此時將
mid作為下限相當于將low作為下限待逞，因此陷入無盡的循環(huán)甥角。流程表示為應對這種情況网严，在選定下一次的查詢范圍時，對
mid做加/減1調(diào)整嗤无。加/減1調(diào)整之后震束，low的值加1，與high相同当犯，有垢村，在進行下次遞歸時，或者
mid-1作為上限嚎卫，或者mid+1作為下限嘉栓，則在下一次遞歸時會出現(xiàn)的情況，這種情況也就是代碼需要首先處理的
，證明值
k不在序列a中侵佃。流程表示為
二分法使得在ordered array中查找復雜度從降到了
麻昼。
Randomized Quick-Selection隨機快速查找
略
Reference
1 Data Structures and Algorithms in Python, Goodrich and etc
