ROSALIND｜Binary Search (BINS)

發表於

給定長度為 n 的嚴格遞增數列，求指定數字在此數列的位置。

Given: Two positive integers $n \leq 10^5$ and $m \leq 10^5$, a sorted array $A[1..n]$ of integers from $-10^5$ to $10^5$, and a list of $m$ integers $-10^5 \leq k_1, k_2, \ldots, k_m \leq 10^5$.

Return: For each $k_i$, output an index $1 \leq j \leq n$ such that $A[j] = k_i$, or “$-1$” if there is no such index.

(https://rosalind.info/problems/bins/)

題目要求我們在數列中尋找特定數字的位置。在沒有額外資訊的情況下，只能遍歷整個數列，所以搜尋時間與數列長度成正比。

反之，額外資訊能幫助我們判斷不可能存在目標數字的位置，減少搜尋時間。舉例來說，如果已知位置及數字的雜湊關係，便能在固定時間內找到目標數字。

如果數列已經過排序，則可以採用二分搜尋。簡言之，搜尋時先比較目標與數列中央的數字，若兩者不相等，則排除不可能包含目標的另一半數列。每一輪搜尋都排除一半的數列，直到找到目標或窮盡剩餘的數列。

二分搜尋可以用迴圈或遞迴實作，關鍵是用 left 和 right 紀錄待搜尋範圍，並且在比較目標與中央數字後更新此範圍。

兩種寫法類似，但我比較習慣迴圈寫法。畢竟每輪搜尋的操作只有比較數字大小，即使沒用遞迴，程式碼還是很好懂。另外，雖然在這題目的尺度內不是問題，遞迴有深度限制，呼叫副程式的次數達到極限會報錯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 以迴圈實作
def bins(l, key):
    left, right = 0, len(l) - 1
    while left <= right:
        mid = (left + right) // 2
        if l[mid] == key:
            return mid
        elif l[mid] < key:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 以遞迴實作
def bins(l, key):
    def helper(l, key, left, right):
        if left > right:
            return -1
        mid = (left + right) // 2
        if l[mid] == key:
            return mid
        elif l[mid] < key:
            return helper(l, key, mid + 1, right)
        else:
            return helper(l, key, left, mid - 1)
    return helper(l, key, 0, len(l) - 1)

最後討論幾個練習時想過的問題。Rosalind 雖然有提供數列的長度，不過 Python list len() 的時間複雜度為 $O(1)$（可參考 Cost of len() function），可以取代數列長度資訊。

另外，在這個寫法裡如果數列長度為偶數，會以數列中央那對數字裡較小者為代表，即程式碼這段： mid = (left + right) // 2。不過其實用較大的數字當代表也可以，mid = (left + right + 1) // 2。

因為每次比對都會逐步更新待搜尋的範圍（left + 1 以及 right -1），即使分割時沒有像切蛋糕一樣精準或是含有重複的數字，後續也不會漏掉實際存在的目標數字。