當前位置:成語大全網 - 新華字典 - Python:關於有序序列元素查找

Python:關於有序序列元素查找

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