Python 中的二分搜索

本教程將學習如何使用 Python 應用二分搜索演算法來查找元素在給定列表中的索引位置。

介紹

二分搜索是一種在列表中查找特定元素的演算法。假設我們有一個包含一千個元素的列表，我們需要得到一個特定元素的索引位置。我們可以使用二分搜索演算法非常快速地找到元素的索引位置。

有許多搜索演算法，但二分搜索是其中最受歡迎的。

列表中的元素必須經過排序才能應用二分搜索演算法。如果元素沒有排序，那麼首先排序它們。

讓我們理解二分搜索的概念。

二分搜索的概念

在二分搜索演算法中，我們可以使用以下方法找到元素位置。

遞歸方法
迭代法

分治法技術之後是遞歸方法。在這個方法中，一個函數一次又一次地調用自己，直到它在列表中找到一個元素。

一組語句被重複多次，以在迭代方法中找到元素的索引位置。和循環用於完成該任務。

二分搜索比線性搜索更有效，因為我們不需要搜索每個列表索引。必須排序列表，以實現二分搜索演算法。

讓我們一步一步實施二分搜索。

我們有一個排序的元素列表，我們正在尋找索引位置 45。

【12、24、32、39、45、50、54】

因此，我們在列表中設置了兩個指針。一個指針用於表示較小的值低，第二個指針用於表示最高的值高。

接下來，我們計算數組中中間元素的值。


mid = (low+high)/2
Here, the low is 0 and the high is 7.
mid = (0+7)/2
mid = 3 (Integer)

現在，我們將把搜索到的元素與中間索引值進行比較。在這種情況下， 32 不等於 45。所以我們需要做進一步的對比，找到元素。

如果我們搜索的數字等於 mid。然後返回中間否則進入下一步比較。

要搜索的數字大於中間的數字，我們將 n 與中間右側元素的中間元素進行比較，並將低設置為低=中間+ 1。

否則，將 n 與中間左側元素的中間元素進行比較，將高設置為高=中間 1。

重複以上步驟，直到找到我們正在搜索的號碼。

用 Python 實現一個二分搜索

首先，我們用迭代法實現一個二分搜索。我們將重複一組語句并迭代列表中的每一項。我們將找到中間值，直到搜索完成。

下面我們來了解一下迭代法的程序。

Python 實現


# Iterative Binary Search Function method Python Implementation
# It returns index of n in given list1 if present, 
# else returns -1 
def binary_search(list1, n):
    low = 0
    high = len(list1) - 1
    mid = 0

    while low <= high:
        # for get integer result 
        mid = (high + low) // 2

        # Check if n is present at mid 
        if list1[mid] < n:
            low = mid + 1

        # If n is greater, compare to the right of mid 
        elif list1[mid] > n:
            high = mid - 1

        # If n is smaller, compared to the left of mid
        else:
            return mid

            # element was not present in the list, return -1
    return -1

# Initial list1
list1 = [12, 24, 32, 39, 45, 50, 54]
n = 45

# Function call 
result = binary_search(list1, n)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in list1")

輸出:

Element is present at index 4

說明:

在上面的程序中-

我們創建了一個名為 binary_search() 的函數，該函數接受兩個參數——一個要排序的列表和一個要搜索的數字。
我們已經聲明了兩個變數來存儲列表中的最低值和最高值。低值被賦予初始值 0，高值被賦予透鏡(列表 1) – 1，中間值為 0。
接下來，我們已經聲明了 while 循環，條件是最低的等於並且小於最高的While循環將迭代，如果還沒有找到數字的話。
在 While循環中，我們找到中間值，並將索引值與我們正在搜索的數字進行比較。
如果中間索引的值小於 n ，我們將中間值增加 1，並將其分配給搜索移動到左側。
否則，降低中間值並將其分配到高電平。搜索移動到右側。
如果 n 等於中間值，則返回中間。
直到低電平等於且小於高電平時，才會出現這種情況。
如果我們到達函數的末尾，那麼該元素不在列表中。我們向調用函數返回-1。

讓我們理解二分搜索的遞歸方法。

遞歸二分搜索

遞歸方法可用於二分搜索。在本文中，我們將定義一個遞歸函數，它會一直調用自己，直到滿足條件。

讓我們使用遞歸函數來理解上面的程序。

Python 程序


# Python program for recursive binary search.
# Returns index position of n in list1 if present, otherwise -1
def binary_search(list1, low, high, n): 

   # Check base case for the recursive function
   if low <= high:

      mid = (low + high) // 2

      # If element is available at the middle itself then return the its index
      if list1[mid] == n: 
         return mid 

      # If the element is smaller than mid value, then search moves
      # left sublist1
      elif list1[mid] > n: 
         return binary_search(list1, low, mid - 1, n) 

      # Else the search moves to the right sublist1
      else: 
         return binary_search(list1, mid + 1, high, n) 

   else: 
      # Element is not available in the list1
      return -1

# Test list1ay 
list1 = [12, 24, 32, 39, 45, 50, 54]
n = 32

# Function call 
res = binary_search(list1, 0, len(list1)-1, n) 

if res != -1: 
   print("Element is present at index", str(res))
else: 
   print("Element is not present in list1")

輸出:

Element is present at index 2

解釋

上面的程序與前面的程序相似。我們聲明了一個遞歸函數及其基本條件。條件是最低值小於或等於最高值。

我們像上一個程序一樣計算中間的數字。
我們使用了 if 語句來處理二分搜索。
如果中間值等於我們要找的數字，則返回中間值。
如果中間值小於該值，我們將再次查看遞歸函數 binary_search() ，並將中間值增加 1 並賦給 low。
如果中間值大於我們正在查看的值，那麼我們的遞歸函數 binary_search() 再次將中間值減少 1，並將其指定為低。

在最後一部分，我們已經寫好了我們的主程序。和之前的程序一樣，唯一不同的是我們在 binary_search() 函數中傳遞了兩個參數。

這是因為我們不能在遞歸函數中將初始值分配給低、高和中。每次調用遞歸時，這些變數的值都會被重置。那會給出錯誤的結果。

複雜性

對於最佳情況，二分搜索演算法的複雜度為 O(1) 。如果我們正在尋找的元素在第一次比較中找到，就會發生這種情況。 O(logn) 是二分搜索最差和平均的情況複雜性。這取決於為找到我們要找的元素而進行的搜索次數。

結論

二分搜索演算法是搜索列表中元素的最有效、最快速的方法。它跳過了不必要的比較。顧名思義，搜索分為兩部分。它集中在列表的一側，接近我們正在搜索的數字。

我們已經討論了兩種方法來找到給定數字的索引位置。

原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/301881.html