資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python 陣列元素搜尋程式
在 Python 中，主要使用兩種搜尋演算法。第一種是線性搜尋，第二種是二分搜尋。
這兩種技術主要用於從給定陣列或列表中搜索元素。在搜尋元素時，任何演算法都可以遵循兩種方法。一種是遞迴方法，另一種是迭代方法。讓我們討論這兩種演算法的兩種方法，並解決類似的問題。
線性搜尋
線性搜尋技術也稱為順序搜尋。“順序搜尋”的名稱含義完全符合該搜尋演算法所遵循的過程。這是一種用於在 Python 的陣列或列表中查詢元素的方法或技術。
它被認為是所有其他搜尋演算法中最簡單、最容易的一種。但是，該演算法的唯一缺點是效率不高。這就是不經常使用線性搜尋的主要原因。
演算法
步驟 1 − 它只是透過將所需元素與給定陣列中的每個元素進行比較，按順序搜尋元素。
步驟 2 − 如果找到所需元素，則會向用戶顯示元素的索引或位置。
步驟 3 − 如果陣列中不存在該元素，則會通知使用者未找到該元素。透過這種方式，演算法得到處理。
通常，線性搜尋演算法對於大小小於或等於 100 的小型陣列或小型列表比較合適且高效，因為它會檢查並與每個元素進行比較。
如果所需元素位於陣列的最後位置，則會消耗更多時間。
線性搜尋演算法的最佳情況時間複雜度為“O(1)”。在這種情況下，元素將位於陣列的第一個位置，即索引為“0”。
線性搜尋演算法的平均情況時間複雜度為“O(n)”。在這種情況下，元素將位於陣列的中間位置，即索引為“(n – 1) / 2”或“((n – 1) / 2) + 1”。
線性搜尋演算法的最壞情況時間複雜度為“O(n)”。在這種情況下，元素將位於陣列的最後位置，即索引為“n-1”。
示例
在下面的示例中，我們將學習使用線性搜尋在陣列中搜索元素的過程。
def iterative_linear( arr, n, key_element):
for x in range(n):
if(arr[x] == key_element):
return x
return -1
arr = [2, 3, 5, 7, 9, 1, 4, 6, 8, 10]
max_size = len(arr)
key = 8
result = iterative_linear(arr, max_size - 1, key)
if result != -1:
print ("The element", key," is found at the index " ,(result), "and in the ", (result+1), "position")
else:
print ("The element %d is not present in the given array" %(key))
輸出
上述程式的輸出如下所示：
The element 8 is found at the index 8 and in the 9 position
示例（遞迴）
在下面的示例中，我們將學習使用遞迴方法的線性搜尋在陣列中搜索元素的過程。
def recursive_linear( arr, first_index, last_index, key_element):
if last_index < first_index:
return -1
if arr[first_index] == key_element:
return first_index
if arr[last_index] == key_element:
return last_index
return recursive_linear(arr, first_index + 1, last_index - 1, key_element)
arr = [2, 3, 5, 7, 9, 1, 4, 6, 8, 10]
max_size = len(arr)
key = 8
result = recursive_linear(arr, 0, max_size - 1, key)
if result != -1:
print ("The element", key," is found at the index " ,(result), "and in the ", (result+1), "position")
else:
print ("The element %d is not present in the given array" %(key))
輸出
上述程式的輸出如下所示：
The element 8 is found at the index 8 and in the 9 position
二分搜尋
二分搜尋演算法與線性搜尋演算法完全不同。它遵循完全不同的程式來從陣列中搜索元素。它通常只考慮排序後的陣列。
如果陣列在某些情況下未排序，則會對陣列進行排序，然後開始二分搜尋演算法的過程。一旦二分搜尋演算法考慮了陣列，它就會先對其進行排序，然後將演算法應用於陣列。
演算法
步驟 1 − 排序陣列是首先執行的步驟。
步驟 2 − 排序陣列後，陣列被視為兩半。一半是從第一個元素到排序陣列的中間元素，另一半是從中間元素後的元素到排序陣列的最後一個元素。
步驟 3 − 將關鍵字元素（要搜尋的元素稱為關鍵字元素）與排序陣列的中間元素進行比較。
步驟 4 − 如果關鍵字元素小於或等於排序陣列的中間元素，則忽略後半部分的元素，因為關鍵字元素小於中間元素。因此，該元素肯定位於第一個元素和中間元素之間。
步驟 6 − 如果關鍵字元素大於中間元素，則忽略排序陣列的前半部分，並考慮從中間元素到最後一個元素的元素。
步驟 7 − 從這些元素中，再次將關鍵字元素與減半陣列的中間元素進行比較，並重復相同的過程。如果關鍵字元素大於減半陣列的中間元素，則忽略前半部分。
步驟 8 − 如果關鍵字元素小於或等於減半陣列的中間元素，則忽略減半陣列的後半部分。透過這種方式，相應地搜尋陣列的任一半中的元素。
因此，與線性搜尋相比，複雜度減少了一半或超過一半，因為在第一步本身就會刪除或不考慮一半的元素。二分搜尋的最佳情況時間複雜度為“O(1)”。二分搜尋的最壞情況時間複雜度為“O(logn)”。這就是二分搜尋演算法的工作原理。讓我們考慮一個例子，並應用二分搜尋演算法來找出陣列中存在的元素中的關鍵字元素。
示例
在這個例子中，我們將學習使用遞迴方法的二分搜尋在陣列中搜索元素的過程。
def recursive_binary(arr, first, last, key_element):
if first <= last:
mid = (first + last) // 2
if arr[mid] == key_element:
return mid
elif arr[mid] > key_element:
return recursive_binary(arr, first, mid - 1, key_element)
elif arr[mid] < key_element:
return recursive_binary(arr, mid + 1, last, key_element)
else:
return -1
arr = [20, 40, 60, 80, 100]
key = 80
max_size = len(arr)
result = recursive_binary(arr, 0, max_size - 1, key)
if result != -1:
print("The element", key, "is present at index", (result), "in the position", (result + 1))
else:
print("The element is not present in the array")
輸出
上述程式的輸出如下所示：
The element 80 is found at the index 3 and in the position 4
示例
在這個例子中，我們將學習使用迭代方法的二分搜尋在陣列中搜索元素的過程。
def iterative_binary(arr, last, key_element):
first = 0
mid = 0
while first <= last:
mid = (first + last) // 2
if arr[mid] < key_element:
first = mid + 1
elif arr[mid] > key_element:
last = mid - 1
else:
return mid
return -1
arr = [20, 40, 60, 80, 100]
key = 80
max_size = len(arr)
result = iterative_binary(arr, max_size - 1, key)
if result != -1:
print("The element", key, "is present at index", (result), "in the position", (result + 1))
else:
print("The element is not present in the array")
輸出
上述程式的輸出如下所示：
The element 80 is found at the index 3 and in the position 4
這就是二分搜尋演算法的工作原理。根據起主要作用的時間複雜度概念，我們肯定可以說二分搜尋演算法比線性搜尋演算法更有效。透過這種方式，可以使用這種型別的演算法搜尋陣列的元素。雖然解決問題的過程不同，但結果不會波動。這是使用多種演算法來檢查輸出一致性的一種優勢。
6000+ 次瀏覽
