Python程式在數組中搜尋元素

在Python中，主要使用兩種搜尋演算法。其中，第一個是線性搜索，第二個是二分搜索。

這兩種技術主要用於從給定數組或給定列表中搜尋元素。在搜尋元素時，任何類型的演算法都可以遵循兩種方法。其中一種是遞歸方法，另一種是迭代方法。讓我們討論兩種方法中的兩種演算法並解決類似的問題。

線性搜尋

線性搜尋技術也稱為順序搜尋。 「順序搜尋」這個名稱的含義絕對是由該搜尋演算法遵循的過程來證明的。它是一種方法或技術，用於在 Python 中查找數組或列表中的元素。

它被認為是所有其他搜尋演算法中最簡單和最容易的。，這個演算法的唯一缺點是效率不高。這就是為什麼不經常使用線性搜尋的主要原因。

演算法

• Step 1 - 它僅透過將所需元素與給定數組中存在的每個元素進行比較來按順序搜尋元素。

• ##步驟2 - 如果找到所需的元素，將基礎元素的索引或位置顯示給使用者。

• ##Step 3

  - 如果陣列中不存在該元素，則會通知使用者未找到該元素。這樣，演算法就處理完了。

一般來說，線性搜尋演算法對於小於或等於100的小型陣列或小型列表來說比較合適且高效，因為它會檢查並比較每個元素。

如果所需的要素定位到倉庫的最後位置，會耗費更多的時間。
線性搜尋演算法在最佳情況下的時間複雜度為「 O( 1 ) 」。在這種情況下，基本上將定位陣列的第一個位置，即索引為「 0 」。
線性搜尋演算法在平均情況下的時間複雜度為「O(n)」。在這種情況下，元素將出現在陣列的中間位置，即索引為“ ( n – 1 ) / 2 ” 或“ (( n – 1 ) / 2 ) 1 ”。
#線性搜尋演算法在最壞情況下的時間複雜度是「O(n)」。在這種情況下，該元素將出現在陣列的最後一個位置，即索引為「 n-1 」。

• # ＃＃＃例＃＃＃
在下面的範例中，我們將學習使用線性搜尋在記憶體中尋找元素的過程。

雷雷 ＃＃＃輸出＃＃＃

上述程式的輸出如下：

雷雷

範例（遞迴）

在下面的範例中，我們將學習使用增量方法在陣列中進行線性搜尋的過程。

雷雷 ＃＃＃輸出＃＃＃

上述程式的輸出如下：

雷雷

二分查找

二分查找演算法與線性查找演算法相當不同。它遵循完全不同的過程來搜尋陣列中的元素。它通常只考慮陣列陣列。

如果陣列在某些情況下沒有排序，則對搜尋陣列進行排序，然後開始二分演算法的過程。一旦陣列被二分搜尋考慮演算法，它首先被排序，然後演算法被陣列分配。

演算法

##步驟1

- 對叢集進行排序是第一步。

##Step 2

- 陣列排序後，陣列被視為兩半。一半是從排序數組的第一個元素到中間元素，後半部是從排序數組的中間元素之後的元素到最後一個元素。

• ##Step 3

  - 將鍵元素（要搜尋的元素稱為鍵元素）與排序數組的中間元素進行比較。

• Step 4

  - 如果鍵元素小於或等於排序數組的中間元素，則後半部元素將進一步忽略，因為鍵元素小於中間元素。因此，該元素肯定必須出現在第一個元素和中間元素之間。

• ##Step 6 - 如果鍵元素大於中間元素，則忽略已排序數組的前半部分，並考慮從中間元素到最後一個元素的元素。

• ##Step 7 - 在這些元素中，再次將關鍵元素與減半數組的中間元素進行比較，並重複相同的過程。如果關鍵元素大於減半數組的中間元素，則忽略前半部。

• 第8步 - 如果关键元素小于或等于被分割数组的中间元素，则被分割数组的后半部分将被忽略。通过这种方式，元素将在数组的任意一半中进行搜索。

因此，与线性搜索相比，复杂度减少了一半或更多，因为有一半的元素将在第一步中被移除或不被考虑。二分搜索的最佳情况时间复杂度为“O(1)”。二分搜索的最坏情况时间复杂度为“O(logn)”。这就是二分搜索算法的工作原理。让我们考虑一个例子，并应用二分搜索算法来找出数组中的关键元素。

Example

In this example, we are going to learn about the process of searching an element in an array using Binary search in recursive approach.

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") 

Output

上述程序的输出如下：

The element 80  is found at the index 3 and in the position 4

Example

In this example, we are going to learn about the process of searching an element in an array using Binary search in iterative approach.

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")

Output

上述程序的输出如下：

The element 80  is found at the index 3 and in the position 4

这是二分搜索算法的工作原理。根据时间复杂度的概念，我们可以肯定二分搜索算法比线性搜索算法更高效，时间复杂度在其中起着重要的作用。通过使用这种类型的算法，可以搜索数组中的元素。尽管用于解决问题的过程不同，但结果不会波动。这是使用多种算法检查输出一致性的一个优点。

以上是Python程式在數組中搜尋元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！