1 引言
有序序列元素查找是python算法中典型且重要的技能,通過對有序序列元素查找的學習,我們可以更快的解決關於有序序列查找的相關問題,也可以更好的體現出我們的解題思維邏輯能力和提高代碼水平。
查找元素。壹般地,我們可以用for循環進行遍歷,再用if語句進行查找。相對於for循環,二分法更加方便。二分法思想 對於已按照關鍵字排序的序列,經過壹次比較後,可將序列分割成兩部分,然後只在有可能包含待查找元素的壹部分中繼續查找,並根據試探結果繼續分割,逐步縮小查找範圍,直至找到或找不到為止。
2 問題描述
示例:如何查找有序序列中某壹的元素
輸入:[1,2,3,4,5,6,……,100] 61 #查找的元素
輸出:61
3 算法描述
在這裏我們主要使用二分法查找。二分法主要是與給定的壹列序數中的中位數進行比較,然後再選取範圍進行查找。如在[1,2,3,4,……,100]中查找61。先取1—100之間的中位數50進行比較,因為50比61小,所以排除1—50之間的數,再用51—100之間的中位數75進行比較,因為75大於61‘所以排除75—100的元素。然後反復地用這個方法排除多余的元素,直到剩下需要查找的元素(61)。
4 結語
有序序列中元素的查找有兩種方法:壹是用for循環進行遍歷查找。二是二分法進行查找。對於會執行很多次的查找時采用二分法比較方便。
附件
def my_func(my_list, searched_number): #二分法
start_number_index = 0
end_number_index = len(my_list) - 1
while start_number_index <= end_number_index:
mid_number_index = (start_number_index = end_number_index) // 2
mid_number = my_list[mid_number_index]
if mid_number < searched_number:
start_number_index = mid_number_indexn+ 1
elif mid_number > searched_number:
end_number_index = mid_number_index - 1
else:
return '找到了需要查找的數字%d'% searched_number
my_list = list(range(1,101))
searched_number = 61
print(my_func(my_list, mid_number))# 結果 找到了需要查找的數字 61