以索引形式回傳結果的二分搜索

作為課程的一部分（Coursera 上的演算法工具箱），我正在研究 Python 中的二進制搜索的實作。

挑戰在于創建二進制搜索的實作，該實作回傳陣列中查詢的索引（整數）。例如，如果我用陣列 [1,5,7] 呼叫 Binary Search 并且我的查詢是 5，則 Binary Search 應該回傳 1。如果目標不在陣列中，那么它應該回傳 -1。例如，我給它 [1, 67, 88, 200]，我的目標是 999，那么它應該回傳 -1。

這個問題是在假設所有測驗用例都向它提供已排序且沒有重復的陣列的情況下運行的。

我當前的實作使用輔助函式來實際進行二分搜索。如果可以找到此幫助程式，則回傳目標值本身，如果找不到，則回傳 -1。呼叫助手的主函式獲取結果，如果不是 -1，它會在我在主函式開頭創建的字典中查找原始索引。

在我自己的私人測驗用例中，代碼運行結果正確，但是在提交時，我被告知代碼運行時間太長而被認為是可接受的。

所以我的請求是這樣的：請檢查我的代碼，并幫助我弄清楚如何更改它以更有效地運行。我的代碼發布在下面：

def single_binary_search(keys, target): 
    '''
    Takes an array of integers, keys, and searches for a value, target, in the array.  If the target is found to be 
    within the array, it returns the target value.  Else, it returns -1 if the array is considered invalid or if the
    target value does not exist within the keys array.  
    
    Input: 
        keys: an array of integers sorted in increasing order 
        target: an integer we wish to ascertain is within keys  
    Returns:
        the target value if it is located, or -1 if it is not or if the array is invalid 
    '''
    start = 0 # define start index
    end = len(keys)-1 # define end index
    if end < start: # check if array is invalid or if target is not in keys.  If so, return -1. 
        return -1 
    mp = start   (end-start)//2 # calculate the midpoint index
    if target == keys[mp]: # check to see if the target is at the midpoint.  
        return keys[mp] # return the target value if located in keys
    elif target < keys[mp]: # if target is less than mp, recursively call binary search on the lower array 
        return single_binary_search(keys[:mp], target)
    else:  # if target is greater than the mp, recursively call binary search on the upper array
        return single_binary_search(keys[mp 1:], target)

def binary_search(keys, query): 
    keys_dictionary = {k: v for v, k in enumerate(keys)} # Create a dictionary of keys to track the indices 
    result = single_binary_search(keys, query) # search for the individual query in keys and store the result 
    if result != -1: # if we found the target, use the keys dictionary to look up the index and return it 
        return keys_dictionary[result]
    else: # if the target was not found or the keys array was invalid, return -1
        return result

較早的實作嘗試向函式添加兩個新引數 ,start = 0, end = None但single_binary_search()我放棄了它，因為我一直遇到無休止的遞回，我知道如何通過添加特定if條件來解決例外。

uj5u.com熱心網友回復：

創建引數 keys[:mp] 是一個切片操作，它創建一個副本，并且花費的時間與副本的大小成線性關系。所以你的演算法實際上需要時間 n/2 n/4 n/8 …=O(n)。如果您僅傳遞新子陣列的第一個和最后一個元素的索引，則該演算法將花費對數時間。您可以使用串列并將索引作為引數傳遞。

uj5u.com熱心網友回復：

這是一個更傳統的二分搜索（另見Wikipedia），效果會更好：

def binary_search(keys, query): 
    L, R = 0, len(keys) - 1
    while L <= R:
        M = L   (R - L) // 2
        if keys[M] == query:
            return M
        elif query < keys[M]:
            R = M - 1
        else:
            L = M   1
    return -1

print("keys:", list(range(0,20,2)))
print(14, binary_search(list(range(0,20,2)), 14))
print(15, binary_search(list(range(0,20,2)), 15))
print(-1, binary_search(list(range(0,20,2)), -1))
print(20, binary_search(list(range(0,20,2)), 20))
print(0, binary_search(list(range(0,20,2)), 0))
print(18, binary_search(list(range(0,20,2)), 18))

測驗用例輸出：

keys: [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
14 7
15 -1
-1 -1
20 -1
0 0
18 9

您的實作中的一些問題是切片很昂貴并且最好避免，而且您的字典機制似乎沒有必要，因為二進制搜索對正在搜索的陣列的索引進行操作，因此您不需要做任何額外的作業來獲得匹配的索引（如果有）。

更新：這是一種也可以使用的遞回方法：

def binary_search(keys, query, L = 0, R = None): 
    R = R if R is not None else len(keys) - 1
    M = L   (R - L) // 2
    if L > R:
        return -1
    elif keys[M] == query:
        return M
    elif query < keys[M]:
        R = M - 1
    else:
        L = M   1
    return binary_search(keys, query, L, R)

標籤：Python 算法 表现 搜索 二分搜索

上一篇：R在多個條件下從data.table中獲取價值的最快方法

下一篇：奶牛天課計算