Python教程-在Python中的二分查找

本教程将学习如何使用Python应用二分查找算法来查找给定列表中元素的索引位置。

简介

二分查找是一种用于查找列表中特定元素的算法。假设我们有一个包含一千个元素的列表，并且我们需要获取特定元素的索引位置。使用二分查找算法，我们可以非常快速地找到元素的索引位置。

有许多搜索算法，但二分查找是其中最流行的。

要应用二分查找算法，列表中的元素必须是已排序的。如果元素未排序，则首先对其进行排序。

让我们了解一下二分查找的概念。

二分查找的概念

在二分查找算法中，我们可以使用以下方法找到元素的位置。

递归方法
迭代方法

递归方法采用分而治之的技术。在此方法中，一个函数反复调用自身，直到在列表中找到元素。

在迭代方法中，一组语句被重复执行多次，以查找元素的索引位置。使用while循环来完成此任务。

二分查找比线性查找更有效，因为我们不需要搜索每个列表索引。为了实现二分查找算法，列表必须经过排序。

让我们逐步实现二分查找。

我们有一个已排序的元素列表，我们要查找数字45的索引位置。

[12, 24, 32, 39, 45, 50, 54]

所以，我们在列表中设置了两个指针。一个指针用于表示较小的值，称为low，第二个指针用于表示较大的值，称为high。

接下来，我们计算数组中middle元素的值。

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

现在，我们将搜索的元素与中间索引的值进行比较。在这种情况下，32不等于45。因此，我们需要进行进一步的比较以找到元素。

如果我们要搜索的数字等于中间值，则返回mid，否则继续进行进一步的比较。

如果要搜索的数字大于middle数字，我们将n与mid右侧的元素进行比较，并将low设置为low = mid + 1。

否则，将n与mid左侧的元素进行比较，并将high设置为high = mid - 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()的函数，它接受两个参数 - 已排序的列表和要查找的数字。
我们声明了两个变量来存储列表中的最低值和最高值。low分配了初始值为0，high为len(list1) - 1，mid为0。
接下来，我们声明了一个while循环，其条件是low小于等于high。只要数字尚未找到，while循环将重复执行。
在while循环中，我们找到中值并将索引值与我们要查找的数字进行比较。
如果中间索引的值小于n，我们将中值增加1并赋给low。搜索将移动到左侧。
否则，将中值减小1并赋给high。搜索将移动到右侧。
如果n等于中值，则返回mid。
这将一直持续，直到low小于等于high。
如果我们到达函数的末尾，那么元素不在列表中。我们返回-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并赋给high。

在最后部分，我们编写了主程序，与前一个程序相同，唯一的区别是在binary_search()函数中传递了两个参数。

这是因为我们不能在递归函数中为low、high和mid分配初始值。每次调用递归时，这些变量的值都会被重置。这将导致错误的结果。

复杂性

二分查找算法的复杂性对于最佳情况是O(1)。如果元素在第一次比较中找到，就会发生这种情况。二分查找的最坏和平均情况复杂性为O(logn)。这取决于进行多少次搜索以找到我们要查找的元素。

结论

二分查找算法是在列表中搜索元素的最有效和快速方法。它跳过了不必要的比较。顾名思义，搜索被分为两部分。它专注于接近我们要搜索的数字的一侧列表。

我们已经讨论了找到给定数字的索引位置的两种方法。